Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework

Theodore Athanasopoulos () and Ioannis Minis ()

Annals of Operations Research, 2013, vol. 206, issue 1, 22 pages

Abstract: In many appointment-based logistics systems customer orders may be served within a set of consecutive periods/days (i.e. a period window). In this case, the Multi-Period Vehicle Routing Problem (MPVRP) is relevant, and its efficient solution may lead to significant operational improvements. In this paper we investigate the MPVRP with Time Windows (MPVRPTW). The latter are time intervals within each period of the period window, during which service may be provided to the customer. A general model and an exact method to solve the MPVRPTW are presented. The solution method is based on column generation. Furthermore, two novel, efficient techniques to accelerate the solution procedure of the MPVRPTW are proposed. These techniques exploit the structure of the multi-period setting in order to identify similarities within the different subproblems and, thus, avoid solving every subproblem at each iteration. The experimental study analyzed the performance of the proposed methods systematically for various problem parameters, such as geographical distribution of customers and period window patterns. In most cases, the new methods improve significantly the efficiency of convergence to the optimal solution as compared to the classical method. Copyright Springer Science+Business Media New York 2013

Keywords: Multi-period; Vehicle routing; Column generation; Acceleration techniques for multi-period vehicle routing problem (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-013-1366-8 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:206:y:2013:i:1:p:1-22:10.1007/s10479-013-1366-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-013-1366-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().