Capacitated Open Vehicle Routing Problem with Time Couplings

被引：0

作者：

Idzikowski, Radoslaw ^{[1
]}

机构：

[1] Wroclaw Univ Sci & Technol, Fac Elect, Wybrzeze Wyspianskiego 27, PL-50370 Wroclaw, Poland

来源：

THEORY AND APPLICATIONS OF DEPENDABLE COMPUTER SYSTEMS, DEPCOS-RELCOMEX 2020 | 2020年 / 1173卷

关键词：

Discrete optimization; Tabu search; COVRP; Time windows; SEARCH;

D O I：

10.1007/978-3-030-48256-5_27

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents a case study for a real-life Capacitated Open Vehicle Routing Problem with Time Windows problem. The goal function is the sum of travel times of all vehicles. The mathematical model of the problem is presented. In order to take specific road traffic regulations into account, additional time-couplings constraints are formualated. Two heuristic solving methods are proposed: a greedy algorithm and a tabu search metaheuristic. The methods are tested using data from a real-life forwarding company. The results indicate that tabu provides 3.8% improvement compared to the greedy method.

引用

页码：273 / 282

页数：10

共 12 条

[1] THE TRUCK DISPATCHING PROBLEM [J].

DANTZIG, GB ;

RAMSER, JH .

MANAGEMENT SCIENCE, 1959, 6 (01) :80-91

[2]

Dantzig GB., 1951, Activity Analysis of Production and Allocation, V13, P339

[3] Solving a real-world vehicle routing problem with multiple use of tractors and trailers and EU-regulations for drivers arising in air cargo road feeder services [J].

Derigs, Ulrich ;

Kurowsky, Rene ;

Vogel, Ulrich .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 213 (01) :309-319

[4] A NEW OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS [J].

DESROCHERS, M ;

DESROSIERS, J ;

SOLOMON, M .

OPERATIONS RESEARCH, 1992, 40 (02) :342-354

[5] Local search for vehicle routing and scheduling problems:: Review and conceptual integration [J].

Funke, B ;

Grünert, T ;

Irnich, S .

JOURNAL OF HEURISTICS, 2005, 11 (04) :267-306

[6] THE GENERAL EMPLOYEE SCHEDULING PROBLEM - AN INTEGRATION OF MS AND AI [J].

GLOVER, F ;

MCMILLAN, C .

COMPUTERS & OPERATIONS RESEARCH, 1986, 13 (05) :563-573

[7]

Grabowski J., 2005, algorytm tabu search z multiruchami. Automatyka/Akademia Gorniczo-Hutnicza im. Stanislawa Staszica w Krakowie, V9, P95

[8] The open vehicle routing problem: Algorithms, large-scale test problems, and computational results [J].

Li, Feiyue ;

Golden, Bruce ;

Wasil, Edward .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (10) :2918-2930

[9]

Lin J.H., 2012, A geo-aware and VRP-based public bicycle redistribution system

[10]

Song ZX, 2001, LECT NOTES COMPUT SC, V2121, P79

← 1 2 →