Vehicle routing problem with stochastic travel times including soft time windows and service costs

被引：190

作者：

Tas, Duygu ^{[1
]}

Dellaert, Nico ^{[1
]}

van Woensel, Tom ^{[1
]}

de Kok, Ton ^{[1
]}

机构：

[1] Eindhoven Univ Technol, Sch Ind Engn & Innovat Sci, NL-5600 MB Eindhoven, Netherlands

来源：

COMPUTERS & OPERATIONS RESEARCH | 2013年 / 40卷 / 01期

关键词：

Vehicle routing; Time windows; Stochastic travel times; Service costs; TABU SEARCH; RELIABILITY; STRATEGIES; INSERTION;

D O I：

10.1016/j.cor.2012.06.008

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper studies a vehicle routing problem with soft time windows and stochastic travel times. A model is developed that considers both transportation costs (total distance traveled, number of vehicles used and drivers' total expected overtime) and service costs (early and late arrivals). We propose a Tabu Search method to solve this model. An initialization algorithm is developed to construct feasible routes by taking into account the travel time stochasticity. Solutions provided by the Tabu Search algorithm are further improved by a post-optimization method. We conduct our computational experiments for well-known problem instances. Results show that our Tabu Search method performs well by obtaining very good final solutions in a reasonable amount of time. (C) 2012 Elsevier Ltd. All rights reserved.

引用

页码：214 / 224

页数：11