A mixed integer linear programming formulation for the vehicle routing problem with backhauls

Abstract: The separate delivery and collection services of goods through different routes is an issue of current interest for some transportation companies by the need to avoid the reorganization of the loads inside the vehicles, to reduce the return of the vehicles with empty load and to give greater priority to the delivery customers. In the vehicle routing problem with backhauls (VRPB), the customers are partitioned into two subsets: linehaul (delivery) and backhaul (pickup) customers. Additionally, a precedence constraint is established: the backhaul customers in a route should be visited after all the linehaul customers. The VRPB is presented in the literature as an extension of the capacitated vehicle routing problem and is NP-hard in the strong sense. In this paper, we propose a mixed integer linear programming formulation for the VRPB, based on the generalization of the open vehicle routing problem; that eliminates the possibility of generating solutions formed by subtours using a set of new constraints focused on obtaining valid solutions formed by Hamiltonian paths and connected by tie-arcs. The proposed formulation is a general purpose model in the sense that it does not deserve specifically tailored algorithmic approaches for their effective solution. The computational results show that the proposed compact formulation is competitive against state-of-the-art exact methods for VRPB instances from the literature.

How to cite this paper

 Granada-Echeverri, M., Toro, E & Santa, J. (2019). A mixed integer linear programming formulation for the vehicle routing problem with backhauls.International Journal of Industrial Engineering Computations , 10(2), 295-308.

Refrences

Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., & Shenoi, R. G. (1998). Flight string models for aircraft fleeting and routing. Transportation Science, 32(3), 208-220.
Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.
Bodin, L. D., Golden, B. L., Assad, A., & Ball, M. 0.(1983) Routing and scheduling of vehicles and crews: The state of the art. Computers and Operations Research, 10, 63-21.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.
Chávez, J., Escobar, J., & Echeverri, M. (2016). A multi-objective Pareto ant colony algorithm for the Multi-Depot Vehicle Routing problem with Backhauls. International Journal of Industrial Engineering Computations, 7(1), 35-48.
Chávez, J., Escobar, J., Echeverri, M., & Meneses, C. (2018). A heuristic algorithm based on tabu search for vehicle routing problems with backhauls. Decision Science Letters, 7(2), 171-180.
Doerner, K., Gutjahr, W. J., Hartl, R. F., Strauss, C., & Stummer, C. (2004). Pareto ant colony optimization: A metaheuristic approach to multiobjective portfolio selection. Annals of Operations Research, 131(1-4), 79-99.
Fourer, R., Gay, D. M., & Kernighan, B. W. (1990). A modeling language for mathematical programming. Management Science, 36(5), 519-554.
Goetschalckx, M., & Jacobs-Blecha, C. (1989). The vehicle routing problem with backhauls. European Journal of Operational Research, 42(1), 39-51.
Irnich, S., Schneider, M., & Vigo, D. (2014a). Chapter 9: Four Variants of the Vehicle Routing Problem. In Vehicle Routing: Problems, Methods, and Applications, Second Edition (pp. 241-271). Society for Industrial and Applied Mathematics.
Irnich, S., Toth, P., & Vigo, D. (2014b). Chapter 1: The family of vehicle routing problems. In Vehicle Routing: Problems, Methods, and Applications, Second Edition (pp. 1-33). Society for Industrial and Applied Mathematics.
Koç, Ç., & Laporte, G. (2017). Vehicle Routing with Backhauls: Review and Research Perspectives. Computers & Operations Research.
Mingozzi, A., Giorgi, S., & Baldacci, R. (1999). An exact method for the vehicle routing problem with backhauls. Transportation Science, 33(3), 315-329
Osman, I. H., & Wassan, N. A. (2002). A reactive tabu search meta‐heuristic for the vehicle routing problem with back‐hauls. Journal of Scheduling, 5(4), 263-285.
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58(1), 21-51
Ropke, S., & Pisinger, D. (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3), 750-775.
Santa Chávez, J. J., Echeverri, M. G., Escobar, J. W., & Meneses, C. A. P. (2015). A Metaheuristic ACO to Solve the Multi-Depot Vehicle Routing Problem with Backhauls. International Journal of Industrial Engineering and Management (IJIEM), 6(2), 49-58.
Salhi, S., & Nagy, G. (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the operational Research Society, 50(10), 1034-1042.
Schrage, L. (1981). Formulation and structure of more complex/realistic routing and scheduling problems. Networks, 11(2), 229-232.
Toth, P., & Vigo, D. (1997). An exact algorithm for the vehicle routing problem with backhauls. Transportation Science, 31(4), 372-385.
Toth, P., & Vigo, D. (1999). A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research, 113(3), 528-543.
Toth, P., & Vigo, D. (Eds.). (2002). The vehicle routing problem. Society for Industrial and Applied Mathematics.
Wade, A., & Salhi, S. (2003). An ant system algorithm for the mixed vehicle routing problem with backhauls. In Metaheuristics: computer decision-making (pp. 699-719). Springer, Boston, MA.