Skip to Main content Skip to Navigation
Journal articles

Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem

Abstract : This paper addresses the multitrip Cumulative Capacitated Single-Vehicle Routing Problem (mt-CCSVRP). In this problem inspired by disaster logistics, a single vehicle can perform successive trips to serve a set of affected sites and minimize an emergency criterion, the sum of arrival times. Two mixed integer linear programs, a flow-based model and a set partitioning model, are proposed for small instances with 20 sites. An exact algorithm for larger cases transforms the mt-CCSVRP into a resource-constrained shortest path problem where each node corresponds to one trip and the sites to visit become resources. The resulting problem can be solved via an adaptation of Bellman–Ford algorithm to a directed acyclic graph with resource constraints and a cumulative objective function. Seven dominance rules, two upper bounds and five lower bounds speed up the procedure. Computational results on instances derived from classical benchmark problems for the capacitated VRP indicate that the exact algorithm outperforms a commercial MIP solver on small instances and can solve cases with 40 sites to optimality.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02485533
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, February 20, 2020 - 11:16:54 AM
Last modification on : Tuesday, March 3, 2020 - 3:11:11 PM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Juan Carlos Rivera, Hasan Murat Afsar, Christian Prins. Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem. European Journal of Operational Research, Elsevier, 2016, 249 (1), pp.93-104. ⟨10.1016/j.ejor.2015.08.067⟩. ⟨hal-02485533⟩

Share

Metrics

Record views

49