Article Preview
Top1. Introduction
The vehicle routing problem with backhauls (VRPB) is an extension to the vehicle routing problem (VRP) where two different types of customers exist. The first type consists of linehaul customers, also known as delivery customers, who require a given quantity of product to be delivered. The second type are the backhaul customers, also known as pickup customers, who require a quantity of goods to be picked up and sent back to the depot. Hence, the VRPP is also known as the vehicle routing problem with pickups and deliveries. The goods are transported to or from a single depot by a fleet of homogeneous vehicles. The objective is to find a set of routes with the least cost where all customer demands are satisfied, each customer is visited exactly once, all routes begin and end at the depot, and finally the load on the vehicle at any arc along the route does not exceed the vehicle capacity.
The VRPB models in the literature either restrict backhauls to be visited once all linehauls have been served, the classical VRPB, or allow a mix of linehaul and backhaul customers along the routes, the mixed VRPB. The latter problem is also known as the vehicle routing problem with mixed pickups and deliveries, and is closely related to the problem of vehicle routing with simultaneous pickups and deliveries, where each customer can have both a pickup and a delivery load. The focus of our paper is on the mixed VRPB. In the classical VRPB it is only necessary to check that the total linehaul load and the total backhaul load do not separately exceed the total vehicle capacity. In the mixed VRPB it is necessary to check that the vehicle capacity is not exceeded at any arc along the route, since in this problem the vehicle load can either decrease or increase at each customer site depending on whether the customer is a linehaul or a backhaul. The classical case is often solved by matching two partial routes: one containing linehauls and the other backhauls. The mixed case is typically solved by inserting backhauls into linehaul routes. The mixed classical VRPB has not received as much attention in the literature as its counterpart the classical VRPB. This has some practical justification given that many vehicles are rear-loaded and that linehaul customers usually prefer early deliveries while backhaul ones may not object to late deliveries. However, the improved design of vehicles, in particular vehicles that permit side loading, mean that mixed routes are now a much more practical option and therefore worth investigating. Such a motivation is obviously also of interest to the case of simultaneous VRPB. In other words, in the mixed VRPB we are allowed to mix linehaul and backhaul customers within a given route as long as feasibility, in terms of vehicle capacity and time restriction, are not violated. Though such flexibility may provide cheaper scheduling costs, it adds extra difficulties in the checking of the vehicle capacity as the load will now fluctuate along the route.