Solution strategies for the vehicle routing problem with backhauls
- PDF / 361,365 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 76 Downloads / 246 Views
Solution strategies for the vehicle routing problem with backhauls Anand Subramanian1 · Eduardo Queiroga2 Received: 21 June 2019 / Accepted: 28 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The paper concerns the classical vehicle routing problem (VRP) with backhauls (VRPB), which can be seen as a special case of the asymmetric VRP with mixed backhauls (AVRPMB). We tackle the VRPB by: (i) directly applying a state-of-the-art AVRPMB matheuristic for the problem, in which a VRPB instance is transformed into an AVRPMB instance, i.e., the infeasible VRPB arcs are penalized; (ii) adapting the same matheuristic for the VRPB itself, in particular, preventing infeasible moves to be unnecessarily evaluated during the local search and also by only allowing feasible solutions to be explored in all steps of the algorithm; (iii) modifying the set partitioning formulation used in the matheuristic to specifically tackle the VRPB. The three approaches were capable of obtaining all best known solutions for the traditional benchmark instances and the result of two instances were improved. We also compare the performance and scalability of the three strategies for instances with up to 1000 customers. Keywords Vehicle routing · backhauls · Matheuristics
1 Introduction The vehicle routing problem (VRP) with backhauls (VRPB) can be defined as follows. Let G = (V0 , A) be a directed graph, where V0 = L ∪ B ∪ 0 is the vertex set and A = A0L ∪ A L B0 ∪ A B0 is the arc set. Vertex 0 is the the depot, whereas subsets
B
Anand Subramanian [email protected] Eduardo Queiroga [email protected]; [email protected]
1
Departamento de Sistemas de Computação, Centro de Informática, Universidade Federal da Paraíba, Rua dos Escoteiros, Mangabeira, João Pessoa, PB 58055-000, Brazil
2
Instituto de Computação, Universidade Federal Fluminense, Rua Passo da Pátria, São Domingos, Niterói, RJ 24210-240, Brazil
123
A. Subramanian, E. Queiroga
L = {1, . . . , n} and B = {n + 1, . . . , n + m} represent the n linehaul and m backhaul customers, respectively. Linehaul customers (a.k.a. linehauls) have a delivery demand di , i ∈ L, and backhaul customers (a.k.a backhauls) have a pickup demand pi , i ∈ B. Subsets A0L , A L B0 , A B0 correspond, respectively, to the arcs (i) connecting the depot to linehauls, (ii) connecting the linehauls to backhauls and to the depot, and (iii) connecting backhauls to the depot. Each arc a ∈ A has an associated cost ca and there is a set of K homogeneous vehicles with capacity Q. The VRPB consists of finding a set of least-cost routes in such a way that (i) each customer is visited exactly once; (ii) backhaul customers can only be served after all linehaul customers have been visited in a particular route; (iii) a non-empty route must contain at least one linehaul customer; (iv) the capacity of the vehicle is not exceeded; and (v)a route must start and finish at the depot. The VRPB is a classical VRP variant with a broad literature as can be observed in the survey by Ko
Data Loading...
