The Open Vehicle Routing Problem with Decoupling Points

Authors: Atefi, Reza; Salari, MajidCoelho, Leandro C.Renaud, Jacques
Abstract: In this paper we introduce the open vehicle routing problem with decoupling points (OVRP-DP). This practical problem is faced by companies dealing with carriers to ship their goods over large territories. In this case it may be profitable to use more than one carrier to perform a specific expedition: the first one leaves the depot and performs part of the deliveries, drops off all remaining load, and the second carrier continues from that point onwards. This drop off location is called the decoupling point of the route. This problem generalizes the classical OVRP in which each route must be performed by only one carrier. We model this problem using a realistic multi-drop less-than-truckload cost function composed of a nonlinear transportation cost, a detour cost and a drop cost. We have developed a tailored Iterated Local Search (ILS) algorithm which handles the special features of the problem. The efficiency of the ILS was demonstrated by obtaining all best known solutions on a set of classical OVRP instances and improving it for one instance. Then, using real orders and transportation costs obtained from industrial partners, we clearly show the benefit of using decoupling points to optimize transportation costs. The performance of the ILS is analyzed and shown to be very robust and superior to what can be obtained with a commercial solver.
Document Type: Article de recherche
Issue Date: 13 July 2017
Open Access Date: 13 July 2019
Document version: AM
This document was published in: European journal of operational research, Vol. 265 (1), 316–327 (2018)
Alternative version: 10.1016/j.ejor.2017.07.033
Collection:Articles publiés dans des revues avec comité de lecture

Files in this item:
OVRP-DP_EJOR.docx667.01 kBMicrosoft Word XMLView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.