The Vehicle Routing Problem with Backhauls (VRPB) is a VRP in which customers can demand or return some commodities. So in VRPPD it’s needed to take into account that the goods that customers return to the deliver vehicle must fit into it. The critical assumption in that all deliveries must be made on each route before any pickups can be made. This arises from the fact that the vehicles are rear-loaded, and rearrangement of the loads on the tracks at the delivery points is not deemed economical or feasible. The quantities to be delivered and picked-up are fixed and known in advance. VRPB is similar to VRPPD with the restriction that in the case of VRPB all deliveries for each route must be completed before any pickups are made.

Objective

The objective is to find such a set of routes that minimizes the total distance traveled.

Feasibility

A feasible solution of the problem consists of a set of routes where all deliveries for each route are completed before any pickups are made and the vehicle capacity is not violated by either the linehaul or backhaul points assigned to the route.

Formulation

The cost of a route is like in the case of VRP, with the additional restriction that a route is feasible if and only if it is delivery-feasible, pick-up-feasible, and load-feasible. First of all, we shall define ${p}$ as a vector of the customer’s pick-up demand.

• Delivery-feasible: this case means that the total amount of commodities to serve in a route must not exceed the vehicle’s capacity. Given a route ${R_{i} = \left\lbrace v_{0}, v_{1}, …, v_{m+1} \right\rbrace}$ and the vehicle assigned to it with capacity ${C}$, this constraint can be mathematically expressed by: ${C_{d}(v_k) \leq C}$ and ${C_{d}(v_{k+1}) \gt C}$; where ${C_{d}(v_k)}$ is the total quantity of goods delivered to all customers of the path of a route that begins on ${v_{0}}$ (depot) and finish at ${v_{k}}$: ${C_{d}(v_k) = \sum_{v_i \in P(1,v_k)} d_{i}}$. ${P(1,v_{k})}$ denotes the customers visited along the path from the depot until ${v_{k}}$, including customer ${v_{k}}$.
• Pick-up feasible: this constraints ensure that the vehicle has enough capacity to pick-up the goods of all the customers of the route. ${C_{p}(v_k) \leq C}$ and ${C_{p}(v_{k+1}) > C}$; where ${C_{p}(v_k)}$ is the total quantity of goods picked-up from all customers along the path of a route up to and including node ${v_{k}}$, that is: ${C_{p}(v_k) = \sum_{v_{i} \in P(1,v_{k})} p_{i} }$.
• Load-feasible: the vehicle’s capacity can be violated at any node of the route. Such a violation will depend on the sequence of the customers. Let ${L(v_{k})}$ be the vehicle’s load just after leaving customer ${v_{k}}$. Assume that the vehicle leaves the depot with an initial load ${L(1) \leq C}$. Then the vehicle’s load at any point of the route is ${L(v_{k}) = C_{p}(v_{k}) + L(1) – C_{d}(i_{k})}$. The vehicle’s load given by this equation can exceed the vehicle’s capacity. This means that the path becomes infeasible because the vehicle can not perform service at next customer ${v_{k+1}}$ on the path. So a route is load feasible if ${L(v_{k}) \leq C}$ and ${L(v_{k+1} > C)}$.