In the vehicle routing problem with multiple time windows (VRPMTW), a single time window must be selected for each customer from the multiple time windows provided. Compared with classical vehicle routing problems with only a single time window per customer, multiple time windows increase the complexity of the routing problem. To minimize the duration of any given route, we present an exact polynomial time algorithm to efficiently determine the optimal start time for servicing each customer. The proposed algorithm has a reduced worst-case and average complexity than existing exact algorithms. Furthermore, the proposed exact algorithm can be used to efficiently evaluate neighborhood operations during a local search resulting in significant acceleration. To examine the benefits of exact neighborhood evaluations and to solve the VRPMTW, the proposed algorithm is embedded in a simple metaheuristic framework generating numerous new best known solutions at competitive computation times.
Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows
2020-03-01
Hoogeboom , M , Dullaert , W , Lai , D & Vigoa , D 2020 , ' Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows ' , Transportation Science , vol. 54 , no. 2 , pp. 400-416 . https://doi.org/10.1287/trsc.2019.0912
Article (Journal)
Electronic Resource
English
DDC: | 629 |
British Library Online Contents | 2015
|Agents Toward Vehicle Routing Problem With Time Windows
Taylor & Francis Verlag | 2015
|