An exact solution approach for vehicle routing and scheduling problems with soft time windows

被引：98

作者：

Qureshi, A. G. ^{[1
]}

Taniguchi, E. ^{[1
]}

Yamada, T. ^{[1
]}

机构：

[1] Kyoto Univ, Dept Urban Management, Nishikyo Ku, Kyoto 6158540, Japan

来源：

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW | 2009年 / 45卷 / 06期

关键词：

City logistics; Vehicle routing with soft time windows; Column generation; SHORTEST-PATH PROBLEM; OPTIMIZATION ALGORITHM; TABU SEARCH;

D O I：

10.1016/j.tre.2009.04.007

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

A new column generation based exact optimization approach for the vehicle routing and scheduling problem with semi soft time windows (VRPSSTW) is presented. Elementary shortest path problem with resource constraints and late arrival penalties is solved as a subproblem, which rises from the Dantzig-Wolfe decomposition method. Exact solutions of VRPSSTW and hard time windows variant are compared on Solomon's benchmark instances as well as on an instance based on Tokyo road network. It was found that the VRPSSTW solution results in fewer routes thus overall costs are reduced and late arrival penalties contribute only a small fraction to total cost. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：960 / 977

页数：18

共 43 条

[1]

Ahuja RK, 1995, NETWORK FLOWS THEORY

[2] A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows [J].

Alvarenga, G. B. ;

Mateus, G. R. ;

de Tomi, G. .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (06) :1561-1584

[3]

ALVARENGA GB, 2004, P 4 INT C HYBR INT S

[4] Travel time reliability in vehicle routing and scheduling with time windows [J].

Ando, Naoki ;

Taniguchi, Eiichi .

NETWORKS & SPATIAL ECONOMICS, 2006, 6 (3-4) :293-311

[5]

BALAKRISHNAN N, 1993, J OPER RES SOC, V44, P279

[6] Vehicle routing problem with time windows, part 1:: Route construction and local search algorithms [J].

Bräysy, I ;

Gendreau, M .

TRANSPORTATION SCIENCE, 2005, 39 (01) :104-118

[7] Vehicle routing problem with time windows, part II:: Metaheuristics [J].

Bräysy, I ;

Gendreau, M .

TRANSPORTATION SCIENCE, 2005, 39 (01) :119-139

[8] A goal programming approach to vehicle routing problems with soft time windows [J].

Calvete, Herminia I. ;

Gale, Carmen ;

Oliveros, Maria-Jose ;

Sanchez-Valverde, Belen .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177 (03) :1720-1733

[9] Vehicle Routing Problem with elementary shortest path based column generation [J].

Chabrier, A .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (10) :2972-2990

[10]

Cordeau JF, 2002, SIAM MONOG DISCR MAT, P157

← 1 2 3 4 5 →