The dynamic multiperiod vehicle routing problem with probabilistic information

被引：54

作者：

Albareda-Sambola, Maria ^{[1
]}

Fernandez, Elena ^{[1
]}

Laporte, Gilbert ^{[2
]}

机构：

[1] Univ Politecn Cataluna, BarcelonaTech, Dept Estat & Invest Operat, E-08028 Barcelona, Spain

[2] HEC Montreal, Canada Res Chair Distribut Management, Montreal, PQ, Canada

来源：

COMPUTERS & OPERATIONS RESEARCH | 2014年 / 48卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Dynamic vehicle routing; VNS; TRAVELING SALESMAN PROBLEMS; ORIENTEERING PROBLEM; FORMULATION; ALGORITHMS; PROFITS;

D O I：

10.1016/j.cor.2014.02.010

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper introduces the Dynamic Multiperiod Vehicle Routing Problem with Probabilistic Information, an extension of the Dynamic Multiperiod Vehicle Routing Problem in which, at each time period, the set of customers requiring a service in later time periods is unknown, but its probability distribution is available. Requests for service must be satisfied within a given time window that comprises several time periods of the planning horizon. We propose an adaptive service policy that aims at estimating the best time period to serve each request within its associated time window in order to reduce distribution costs. The effectiveness of this policy is compared with that of two alternative basic policies through a series of computational experiments. (C) 2014 Elsevier Ltd. All rights reserved.

引用

页码：31 / 39

页数：9

共 21 条

[1] Competitive analysis for dynamic multiperiod uncapacitated routing problems
Angelelli, Enrico
Speranza, M. Grazia
Savelsbergh, Martin W. P.
[J]. NETWORKS, 2007, 49 (04) : 308 - 317
[2] Optimal solutions for routing problems with profits
Archetti, C.
Bianchessi, N.
Speranza, M. G.
[J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (4-5) : 547 - 557
[3] The capacitated team orienteering and profitable tour problems
Archetti, C.
Feillet, D.
Hertz, A.
Speranza, M. G.
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2009, 60 (06) : 831 - 842
[4] Metaheuristics for the team orienteering problem
Archetti, Claudia
Hertz, Alain
Speranza, Maria Grazia
[J]. JOURNAL OF HEURISTICS, 2007, 13 (01) : 49 - 76
[5] An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation
Baldacci, R
Hadjiconstantinou, E
Mingozzi, A
[J]. OPERATIONS RESEARCH, 2004, 52 (05) : 723 - 738
[6] Dynamic pickup and delivery problems
Berbeglia, Gerardo
Cordeau, Jean-Francois
Laporte, Gilbert
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (01) : 8 - 15
[7] A STOCHASTIC AND DYNAMIC VEHICLE-ROUTING PROBLEM IN THE EUCLIDEAN PLANE
BERTSIMAS, DJ
VANRYZIN, G
[J]. OPERATIONS RESEARCH, 1991, 39 (04) : 601 - 615
[8] Adaptive granular local search heuristic for a dynamic vehicle routing problem
Branchini, Rodrigo Moretti
Armentano, Vinicius Amaral
Lokketangen, Arne
[J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (11) : 2955 - 2968
[9] Traveling salesman problems with profits
Feillet, D
Dejax, P
Gendreau, M
[J]. TRANSPORTATION SCIENCE, 2005, 39 (02) : 188 - 205
[10] Francis PM, 2008, OPER RES COMPUT SCI, V43, P73, DOI 10.1007/978-0-387-77778-8_4

← 1 2 3 →