PhD position: Towards a dynamic vehicle routing problem in cyber-physical systems
14 Octobre 2022
Catégorie : Doctorant
PhD proposal CLEAR-Doc call within the Marie Skłodowska-Curie COFUND programme for the “City of tomorrow”. The subject is dynamic vehicle routing problem in cyber-physical systems/
PhD proposal: Towards a dynamic vehicle routing problem in cyber-physical systems
Keywords:vehicle routing problem, cyber-physical systems, operations research, machine learning, game theory
Recent technological advances have allowed the emergence of cyber-physical systems (CPS) that will profoundly impact the management of production systems, for both goods and services. The transportation of goods in big cities is one of the challenging issue regarding the increase of urban transportation demand for freight (Behiri et al. 2018; Sahli et al. 2022). Indeed, the distributed nature of cyber-physical systems suggests the evolution of decision-making architectures from a hierarchical mode to a heterarchical or hybrid mode. The work of Monostori et al. (2016) highlights the necessary developments of decision-making processes in the case of production systems to take full advantage of the benefits of CPS. The latter benefits concern responsiveness, flexibility, and adaptability to recurrent changes in the environment (representing the decision problem input data). Similarly, transportation systems are also subject to many changes at the operational level regarding the duration of trips, the addition or cancellation of new customers to deliver or the modification of desired delivery dates. Thus, cyber-physical systems offer an opportunity to increase reactivity for vehicle routing problems (VRP) that dominate urban freight distribution.
Vehicle Routing Problem
The vehicle routing problem has been extensively studied in the literature considering different deterministic variants such as the capacitated VRP, time-dependent VRP, periodic VRP, VRP with time windows, VRP with pickup and delivery, VRP with heterogeneous fleet, VRP with multiple depots, or even with backhauls (Lin et al., 2014). More recent variants consider electric vehicles with constraints related to battery charging (Kancharla & Ramadurai, 2020; Kucukoglu et al., 2021).
The evolution of the e-commerce services generates an increase in the dynamics of delivery demands. Hence, in order to take into account the real context it is mandatory to consider the data dynamics when solving the VRP. A state of the art survey related to dynamic VRP is presented in (Pillac et al. 2013). Several objective functions have been considered beyond cost such as service rate, revenue or travel time (Montoya-Torres et al., 2015). Other works approach the problem through its stochastic version so as to integrate the variability of travel time or customer demand (DS-CVRPTW). This problem has been formalized using a multi-agent decision model and a deep neural network to learn the best decision rules (Bono et al., 2021).
Thesis expected contribution
The communication capability of vehicles provides new opportunities for the adaptation and optimization of distribution routes to consider changes in delivery data. To the best of our knowledge, the only work that addresses the evolution of the VRP in a cyber-physical context is that of Lee et al. (2022). However, the proposed approach remains classical as it is a metaheuristic based on Ant Colony (Nested MAX-MIN Ant System) and the innovation lies in the deployment at the scale of the city of Hong Kong in an instrumented environment of sensors allowing data collection.
In this thesis, we propose to better exploit the potential of CPSs and introduce collaborative approaches to ensure a trade-off between decision-making responsiveness and overall delivery performance. Cyber-physical systems bring a shift in the paradigm by providing a more favorable conceptual framework to improve responsiveness that, in the case of a VRP, would allow to take on new customers for each of the vehicles or to adapt the tour according to the traffic condition without restarting the computation from scratch.
1- Review of current literature exploiting collaborative decision strategies and optimization techniques for VRPs
2- Design of an architecture of VRP decision entities in a CPS context. This architecture should promote collaboration between entities in order to generate solutions that respond to changes in the data (new customers, changes in travel times, etc.).
3- Design of novel algorithms adapted to the collaborative approach exploiting tools from game theory (Lakshminarayana et al., 2021), statistical learning (Chafaa et al., 2022) and operations research.
4- Validation of the proposed algorithms using instances from the literature and/or case studies.
The successful candidate will be funded via the CLEAR-Doc call within the Marie Skłodowska-Curie COFUND programme for the “City of tomorrow”. This programme offers three years funding and an attractive gross salary of approximately 2700 euro per month and an attractive research environment (mobility, conference expenses, etc). This scholarship does not cover the university registration fees of approximately 500 per year. The PhD student will be based at the Université Gustave Eiffel and will be a member of GRETTIA/COSYS research lab and of the LIGM research lab of the CNRS situated within the Université Gustave Eiffel campus at the East of Paris and 30 minutes by the RER suburban train from center Paris, France. Within the international partnership with Universidad de La Sabana, Colombia, the PhD student will also have the opportunity to collaborate with the international research group of Prof. J.R. Montoya-Torres.
Start date: September 2023
Dr. Sana BERRAF-BELMOKHTAR (Assoc. Prof. Univ. Gustave Eiffel) - operations research, optimization of production systems of goods and services
Prof. E. Veronica BELMEGA (Prof. Univ. Gustave Eiffel) - distributed wireless and smart-grid systems, self-optimizing networks via online optimization, machine learning and game theory
Prof. Jairo R. MONTOYA-TORRES(Prof. Universidad de La Sabana, Colombia) - optimization, simulation, urban logistics, sustainability
How to apply?
Candidates should hold an MSc degree or equivalent in computer science, electrical engineering, or applied mathematics and have a strong mathematical background. Also, strong programming skills (C/C++, Python, …) are a definite plus.Eligibility condition - International recruitment: To apply, candidates must not have spent more than 12 months in France during the last 3 years.
Interested candidates have to send their detailed CV, academic records (from BSc to MSc level), two academic references and a short motivation letter (one page max) via email to the contact below.Applications will be received until January 31st,2023. Full details can be found below:
Sana BERRAF-BELMOKHTAR (email@example.com)
Behiri, W., Belmokhtar-Berraf, S., Chu, C. (2018). "Urban freight transport using passenger rail network: Scientific issues and quantitative analysis", Transportation Research Part E: Logistics and Transportation Review, 115, 227-245
Bono, G., Dibangoye, J.S., Simonin, O., Matignon, L., Pereyron, F. (2021), “Solving Multi-Agent Routing Problems Using Deep Attention Mechanisms”. IEEE Transactions on Intelligent Transportation Systems,22, 12, 7804-7813.
Chafaa, I., Negrel, R., Belmega, E.V., Debbah, M. (2022), "Self-supervised deep learning for mmWave beam steering exploiting sub-6 GHz channels". IEEE Trans. on Wireless Commun.
Lakshminarayana, S. Belmega, E.V., Poor, H. V. (2021), "Moving-Target Defense Against Cyber-Physical Attacks in Power Grids via Game Theory". IEEE Trans. on Smart Grids.
Kancharla, S.R. , Ramadurai, G. (2020), “Electric vehicle routing problem with non-linear charging and load-dependent discharging”. Expert Systems with Applications, 160 , 113714
Kucukoglu, I., Dewil, R., Cattrysse, D. (2021), “The electric vehicle routing problem and its variations: A literature review”. Computers & Industrial Engineering, 161, 107650
Lee, C.K.M., Ng, C.K., Chung, S.Y., Keung, K.L. (2022), “Cloud-based Cyber-Physical Logistics System with Nested MAX-MIN Ant Algorithm for E-commerce logistics”. Expert Systems with Applications, 211.
Lin, C., Choy, K. L., Ho, G. T. S., Chung, S. H., Lam, H. Y. (2014). “Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications”, 41, 1118–1138.
Monostori, L., Kádár, B., Bauernhansl, T., Kondoh, S.,Kumara, S., Reinhart, G., Sauer, O.,Schuh, G., Sihn, W., Ueda,K. (2016), “Cyber-physical systems in manufacturing”. CIRP Annals, 65 (2), 621-641.
Montoya-Torres, J.R., López Franco, J., Nieto Isaza, S., Felizzola Jiménez, H., Herazo-Padilla, N. (2015), “A literature review on the vehicle routing problem with multiple depots”, Computers & Industrial Engineering, 79, 115-129.
Pillac, V., Gendreau, M., Guéret, C., Medaglia, A. L. (2013), “A review of dynamic vehicle routing problems”. European Journal of Operational Research, 225 (1), 1–11.
Sahli, A., Behiri, W., Belmokhtar-Berraf, S., Chu,C. (2022), “An effective and robust genetic algorithm for urban freight transport scheduling using passenger rail network“, Computers & Industrial Engineering, 173, 108645.