A Branch and Price algorithm for the electric capacitated profitable tour problem with mandatory stops

被引：6

作者：

Cortes-Murcia, David L. ^{[1
]}

Afsar, H. Murat ^{[1
]}

Prodhon, Caroline ^{[1
]}

机构：

[1] Univ Technol Troyes, ICD LOST, 12 Rue Marie Curie,CS 42060, F-10004 Troyes, France

来源：

IFAC PAPERSONLINE | 2019年 / 52卷 / 13期

关键词：

Electric vehicles; Routing problems; Branch-and-price; VEHICLE-ROUTING PROBLEM; ORIENTEERING PROBLEM; CUT ALGORITHM; STRATEGIES;

D O I：

10.1016/j.ifacol.2019.11.424

中图分类号：

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

学科分类号：

0812 ;

摘要：

In this paper, a generalization of the capacitated profitable tour problem is presented. Since recharging time and driver's lunch breaks are commonly considered as an idle time, the aim is to synchronize those activities choosing restaurants where electric vehicles can be charged. Due to visiting restaurants has an associated cost, the problem can also be seen as a problem with location issues. This variant is pertinent especially in a city logistics context. A mathematical model is proposed, as well as a Branch-and-Price algorithm which is able to solve instances with up to 100 customers and 13 restaurants. (C) 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.

引用

页码：1572 / 1577

页数：6

共 26 条

[1] Electric Vehicle Routing Problem with industry constraints: trends and insights for future research [J].

Afroditi, Anagnostopoulou ;

Boile, Maria ;

Theofanis, Sotirios ;

Sdoukopoulos, Eleftherios ;

Margaritis, Dimitrios .

17TH MEETING OF THE EURO WORKING GROUP ON TRANSPORTATION, EWGT2014, 2014, 3 :452-459

[2] Optimal solutions for routing problems with profits [J].

Archetti, C. ;

Bianchessi, N. ;

Speranza, M. G. .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (4-5) :547-557

[3] The capacitated team orienteering and profitable tour problems [J].

Archetti, C. ;

Feillet, D. ;

Hertz, A. ;

Speranza, M. G. .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2009, 60 (06) :831-842

[4] New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem [J].

Baldacci, Roberto ;

Mingozzi, Aristide ;

Roberti, Roberto .

OPERATIONS RESEARCH, 2011, 59 (05) :1269-1283

[5] A branch-and-cut algorithm for the Team Orienteering Problem [J].

Bianchessi, Nicola ;

Mansini, Renata ;

Speranza, M. Grazia .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2018, 25 (02) :627-635

[6] An exact algorithm for team orienteering problems [J].

Boussier, Sylvain ;

Feillet, Dominique ;

Gendreau, Michel .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (03) :211-230

[7] A fast and effective heuristic for the orienteering problem [J].

Chao, IM ;

Golden, BL ;

Wasil, EA .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (03) :475-489

[8] A methodology to evaluate the competitiveness of electric delivery trucks [J].

Davis, Brian A. ;

Figliozzi, Miguel A. .

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2013, 49 (01) :8-23

[9] Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows [J].

Desaulniers, Guy ;

Errico, Fausto ;

Irnich, Stefan ;

Schneider, Michael .

OPERATIONS RESEARCH, 2016, 64 (06) :1388-1405

[10]

Duc-Cuong Dang, 2013, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013. Proceedings, P332, DOI 10.1007/978-3-642-38171-3_23

← 1 2 3 →