Dear colleagues,
Please find below a PhD proposal on a topic mixing Machine learning and Operations research at IMT Mines Alès (France).
Title: Machine Learning for Vehicle Routing Problems
Keywords: Machine Learning, Discrete Optimization, Local Search, Rich Vehicule Routing Problems.Profile and skills required: Master degree with courses related to machine learning and/or combinatorial optimization/operations research, algorithmics + advanced level in C/C++ programming langage.Grants: ~1600 – 1700 euros/month
Location: Alès (France)Project description:
The Vehicle Routing Problem (VRP) is of major importance for the Industry, e.g. transport, supply, and logistics. The topic studied in this thesis is optimization for routing and planning of vehicles, in cases where customers have to be visited with a fleet of vehicles and a pool of technicians for maintenance or delivery operations [1]. Based on recent advances in Machine Learning (in particular Deep Learning [2]), we will study the definition of approaches that take advantage of reinforcement learning techniques to enhance exploration of complex search spaces encountered in this type of planning problem [3,4,5] – similarly to the approach defined in AlphaGo, the Deep Mind solution used to win the best Go players. These approaches allow learning complex invariants that are useful for finding relevant alternatives by reducing the number of alternatives to be evaluated when looking for solutions to (sub-)problems of interest.
In recent years, due to the rapid development of new computing and optimization methods, practitioners have also focused on more realistic VRP variants, which are commonly known as ‘rich VRP ‘[6]. These variants take into account in particular:
• uncertain data (fuzzy or stochastic events),
• real-time data (‘on-line optimization’).
• an important variety of real constraints related to time and space dimensions,
• the scheduling of visits with different temporal constraints, over a given period ‘Periodic VRP’ [7,8],
• taking into account traffic, if not in real time at least in ‘Time dependent VRP’ time bands [9,10],
• stock management [11,12].
Most of these VRP formulations are thus, by definition, dependent on the variable nature of specific components of the problem (e.g., traffic, orders, availability of resources). In this context, we will also study the definition of hybrid approaches able to take advantage of predictive models. Such approaches would enable a better management of the complexities induced by the variabilities attached to the realistic formulations of the VRP problem [13]. We will in particular study the use of supervised and unsupervised learning techniques for the integration of contextual predictions [14].
The data needed for the experimental part of this work could correspond to real tour planning cases provided by GeoConcept, a company specialized in the design and publishing of cartographic and logistical optimization solutions.[1] Hashimoto Hideki, Boussier Sylvain, Vasquez Michel and Wilbaut Christophe, « A GRASP-based approach for technicians and interventions scheduling for telecommunications », Annals of Operations Research,183,1, 143-161, (2011).
[2] LeCun, Y., Bengio, Y., & Hinton, G. Deep learning. Nature, 521(7553), 436 (2015).
[3] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., … & Chen, Y. Mastering the game of go without human knowledge. Nature, 550(7676), 354 (2017).
[4] Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, (2018).
[5] Choong, S. S., Wong, L. P., & Lim, C. P. Automatic design of hyper-heuristic based on reinforcement learning. Information Sciences, 436, 89-107 (2018).
[6] Jose Caceres-Cruz, Pol Arias, Daniel Guimarans, Daniel Riera, Angel A. Juan. « Rich Vehicle Routing Problem: Survey. » , ACM Computing Surveys (CSUR) Volume 47 Issue 2, (2015)
[7] F. Alonso, M. J. Alvarez, and J. E. Beasley. « A tabu search algorithm for the periodic vehicle routing problem with vehicle trips and accessibility restrictions. », Journal of the Operational Research Society, 59:963-976, (2008)
[8] E. Angelelli and M. G. Speranza. « The periodic vehicle routing problem with intermediate facilities. », European Journal of Operational Research, 137:233-247, (2002).
[9] C. Malandraky and M.S. Daskin « Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms » Transportation Science, vol. 26, 185-200, (1992).
[10] S. Ichoua, M. Gendreau, J-Y Potvin, « Vehicle Dispatching With Time-Dependent Travel Times », European Journal of Operational Research. 144, no. 2, 379-396, (2003).
[11] Ann Melissa Campbell, Martin W. P. Savelsberg, « A Decomposition Approach for the Inventory-Routing Problem » ,TRANSPORTATION SCIENCE, Vol. 38, No. 4, 488–502 (2004)
[12] Thierry Benoist, Frédéric Gardi, Antoine Jeanjean, « Randomized local search for real-life inventory routing », TRANSPORTATION SCIENCE, INFORMS (2011)
[13] Kadaba, N., Nygard, K. E., & Juell, P. L.. Integration of adaptive machine learning and knowledge-based systems for routing and scheduling applications. Expert Systems with Applications, 2(1), 15-27, (1991).
[14] Kato, N., Fadlullah, Z. M., Mao, B., Tang, F., Akashi, O., Inoue, T., & Mizutani, K. The deep learning vision for heterogeneous network traffic control: Proposal, challenges, and future perspective. IEEE wireless communications, 24(3), 146-153 (2017).Director: Michel Vasquez (IMT Mines Alès) michel.vasquez@mines-ales.frCandidates must apply on the following online plateform :
https://www.adum.fr/as/ed/voirproposition.pl?langue=gb&site=ISS&matricule_prop=26113
Do not hesitate to contact us if you have any questions.
Sincerely,Sébastien HARISPE Enseignant-Chercheur IMT Mines Alès