Probability estimation and structured output prediction for learning preferences in last mile delivery

被引:4
作者
Canoy, Rocsildes [1 ,5 ]
Bucarey, Victor [2 ,3 ]
Mandi, Jayanta [1 ]
Mulamba, Maxime [1 ]
Molenbruch, Yves [5 ]
Guns, Tias [4 ]
机构
[1] Vrije Univ Brussel, Data Analyt Lab, Brussels, Belgium
[2] Univ Ohiggins, Inst Engn Sci, Rancagua, Chile
[3] Inst Sistemas Complejos Ingn ISCI, Santiago, Chile
[4] Katholieke Univ Leuven, KUL Inst AI, Leuven, Belgium
[5] Vrije Univ Brussel, Mobil Logist & Automot Technol Res Ctr MOBI, Brussels, Belgium
基金
欧洲研究理事会;
关键词
Traveling salesman problem; Preference learning; Structured output prediction;
D O I
10.1016/j.cie.2024.109932
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We study the problem of learning the preferences of drivers and planners in the context of last mile delivery. Given a data set containing historical decisions and delivery locations, the goal is to capture the implicit preferences of the decision -makers. We consider two ways to use the historical data: one is through a probability estimation method that learns transition probabilities between stops (or zones). This is a fast and accurate method, recently studied in a VRP setting. Furthermore, we explore the use of machine learning to infer how to best balance multiple objectives such as distance, probability and penalties. Specifically, we cast the learning problem as a structured output prediction problem, where training is done by repeatedly calling the TSP solver. Another important aspect we consider is that for last mile delivery, every address is a potential client and hence the data is very sparse. Hence, we propose a two -stage approach that first learns preferences at the zone level in order to compute a zone routing; after which a penalty -based TSP computes the stop routing. Results show that the zone transition probability estimation performs well, and that the structured output prediction learning can improve the results further. We hence showcase a successful combination of both probability estimation and machine learning, all the while using standard TSP solvers, both during learning and to compute the final solution; this means the methodology is applicable to other, real -life, TSP variants, or proprietary solvers.
引用
收藏
页数:11
相关论文
共 39 条
[1]  
[Anonymous], 2006, AAAI
[2]  
Applegate D.L., 2011, TRAVELING SALESMAN P
[3]  
BakIr G., 2007, Predicting structured data, DOI DOI 10.7551/MITPRESS/7443.001.0001
[4]  
Bello I., 2017, arXiv
[5]  
Canoy R, 2021, Arxiv, DOI arXiv:2101.03936
[6]   Vehicle Routing by Learning from Historical Solutions [J].
Canoy, Rocsildes ;
Guns, Tias .
PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2019, 2019, 11802 :54-70
[7]  
Ceikute V, 2013, 2013 IEEE 14TH INTERNATIONAL CONFERENCE ON MOBILE DATA MANAGEMENT (MDM 2013), VOL 1, P97, DOI 10.1109/MDM.2013.20
[8]   An inverse optimization approach for a capacitated vehicle routing problem [J].
Chen, Lu ;
Chen, Yuyi ;
Langevin, Andre .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 295 (03) :1087-1098
[9]  
Chen X., 2020, 8 INT C LEARNING REP
[10]  
Chisman J. A., 1975, Computers & Operations Research, V2, P115, DOI 10.1016/0305-0548(75)90015-5