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

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

0.00 Avg rating0 Votes
Article ID: iaor20133947
Volume: 206
Issue: 1
Start Page Number: 1
End Page Number: 22
Publication Date: Jul 2013
Journal: Annals of Operations Research
Authors: ,
Keywords: column generation, time windows
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.

Reviews

Required fields are marked *. Your email address will not be published.