MSCA-COFUND-CLEAR-Doc - PhD Position #CD22-04: Towards a dynamic vehicle routing problem in cyber-physical systems

Cyber-physical systems

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.

Methodology

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.

References

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.