Improved Simulated Annealing Algorithm for Vehicle Routing Problem with Multiple Time Windows using Column Generation

被引：0

作者：

Tu, Siqi ^{[1
]}

Li, Shurong ^{[1
]}

Liu, Zhe ^{[1
]}

Zeng, Derui ^{[1
]}

机构：

[1] Beijing Univ Posts & Telecommun, Automat Sch, Beijing 100876, Peoples R China

来源：

PROCEEDINGS OF THE 39TH CHINESE CONTROL CONFERENCE | 2020年

关键词：

vehicle routing problem with multiple time windows; column generation; improved simulated annealing algorithm; iterated local search with recursion; SHORTEST-PATH PROBLEM; CONSTRAINTS; CAPACITY;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper proposes an improved simulated annealing (ISA) algorithm embedded in column generation to solve the vehicle routing problem with multiple time windows (VRPMTW). Firstly, two mathematical models of the VRPMTW are discussed: mixed integer model and set covering model. Next, the principle of the column generation (CG) algorithm for the set covering model is introduced. In the column generation algorithm, we obtain the optimal solution of VRPMTW by solving the restrict master problem and subproblem. Then, the ISA algorithm which embedded an iterated local search with recursion (ILSR) algorithm is proposed to solve the subproblem. The master problem is solved by cplex. At last, experimental results show that the ISA algorithm can escape the local optimal solution effectively, avoid premature phenomenon and converge quickly.

引用

页码：1649 / 1654

页数：6

共 19 条

[1] Separating capacity constraints in the CVRP using tabu search [J].

Augerat, P ;

Belenguer, JM ;

Benavent, E ;

Corberan, A ;

Naddef, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 106 (2-3) :546-557

[2] Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints [J].

Baldacci, Roberto ;

Mingozzi, Aristide ;

Roberti, Roberto .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 218 (01) :1-6

[3] Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands [J].

Calvet, Laura ;

Wang, Dandan ;

Juan, Angel ;

Bove, Lluc .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2019, 26 (02) :458-484

[4]

Chen C, 2018, 2018 INTERNATIONAL CONFERENCE ON SENSING, DIAGNOSTICS, PROGNOSTICS, AND CONTROL (SDPC), P781, DOI [10.1109/SDPC.2018.8664999, 10.1109/SDPC.2018.00152]

[5] THE TRUCK DISPATCHING PROBLEM [J].

DANTZIG, GB ;

RAMSER, JH .

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

[6]

Darwish Saad M., 2020, International Conference on Advanced Machine Learning Technologies and Applications (AMLTA2019). Advances in Intelligent Systems and Computing (AISC 921), P133, DOI 10.1007/978-3-030-14118-9_14

[7] An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems [J].

Feillet, D ;

Dejax, P ;

Gendreau, M ;

Gueguen, C .

NETWORKS, 2004, 44 (03) :216-229

[8] A tutorial on column generation and branch-and-price for vehicle routing problems [J].

Feillet, Dominique .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2010, 8 (04) :407-424

[9] The period vehicle routing problem with service choice [J].

Francis, Peter ;

Smilowitz, Karen ;

Tzur, Michal .

TRANSPORTATION SCIENCE, 2006, 40 (04) :439-454

[10] A heuristic for cumulative vehicle routing using column generation [J].

Gaur, Daya Ram ;

Singh, Rishi Ranjan .

DISCRETE APPLIED MATHEMATICS, 2017, 228 :140-157

← 1 2 →