A Rich Vehicle Routing Problem with Multiple Trips and Driver Shifts

This study is concerned with a rich vehicle routing problem (RVRP) encountered at a Belgian transportation company in charge of servicing supermarkets and hypermarkets belonging to a franchise. The studied problem can be classified as a one-to-many-to-one pick-up and delivery problem, where there is a single depot from which all delivery customers are served and to which every pick-up demand must be carried back (Gutiérrez-Jarpa et al., 2010). The delivery and backhaul customers are considered to be two disjoint sets, where on a given route backhaul customers can be visited only after all delivery customers are served. Split deliveries and pick-ups are not allowed. The service at a customer must start within the given time window of the customer. However, it is not possible to serve a customer with every available vehicle, since the vehicles at the company’s disposal are of different types according to which the capacity changes. Therefore, our problem can be classified also as a heterogeneous fleet vehicle routing problem with customer-vehicle incompatibilities (Ceselli et al., 2009). The problem at hand requires that the same vehicle may be assigned to several routes, which leads to a multiple-trip RVRP. Furthermore, driver shifts are taken into account so that each vehicle of the fleet starts servicing the customers when the shift of the assigned driver starts. The shift duration is the same for all drivers. If the service of the vehicle exceeds SH, an overtime cost incurs to the transportation company. In such a case, a vehicle can be used during at most a fixed length of time. In addition to the vehicles of the company’s own fleet (i.e. internal vehicles), there is a possibility to request external vehicles for servicing some customers. External vehicles can be used for a fixed maximum amount of time and can start servicing customers at any desired time. A fixed reservation cost and distance and time based variable costs are incurred in the case of an external vehicle, while only distance based variable costs are incurred in the case of an internal vehicle.
We employ a binary integer linear programming formulation in order to model our problem. The first constraint set ensures that each customer is visited at least once by either an internal or external vehicle. With the second constraint set, it is guaranteed that each internal vehicle is assigned to at most one tour. The last two constraint sets are the binary restrictions on the assignment variables. In order to solve the problem, we first relax the binary restrictions on the assignment variables and develop a column generation procedure, where we obtain two pricing problems, one for internal vehicles and the other one for external vehicles. The pricing problem of each internal vehicle can be formulated as an elementary shortest path problem with resource constraints, which can be solved using a dynamic programming algorithm based on a bounded bi-directional search (Righini and Salani, 2008). However, since an external vehicle can start the service at any point in time and is paid based on its total travel time, the second pricing algorithm has to take into account an infinite number of Pareto-optimal states (Liberatore et al., 2011). We discuss the efficient solution of the pricing subproblems and present preliminary computational results.