Abstract
Managing a fleet of vehicles under uncertainty requires careful planning and adaptability. We consider a ride-hailing problem where the operator manages vehicle repositioning to maximize responsiveness. This paper introduces a supervised learning pipeline that uses past trip data to reposition vehicles while adapting to fleet activity, a geographical zone, and seasonal or daily request variation. The pipeline incorporates trip features, such as medical motives of transportation for ambulances and the time and location of the trips. This provides a better estimate of the probability that a given vehicle will be required in a particular sector and provides insights into which events and trip features should be incorporated into the decision-making process for better fleet management and improved reactivity. This tool has been developed for, and used by, operators of an ambulance company in Belgium. Using predictors for ambulance repositioning reduces at least 10% of the overall fleet reaction distance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., Rus, D.: On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. Natl. Acad. Sci. 114(3), 462–467 (2017). https://doi.org/10.1073/pnas.1611675114
Arulkumaran, K., Deisenroth, M.P., Brundage, M., Bharath, A.A.: A brief survey of deep reinforcement learning (2017). http://arxiv.org/abs/1708.05866
Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur. J. Oper. Res. 290(2), 405–421 (2021)
Bertsimas, D., Jaillet, P., Martin, S.: Flexbus: improving public transit with ride-hailing technology. Dow Sustainability Fellowship (2017). http://sustainability.umich.edu/media/files/dow/Dow-Masters-Report-FlexBus.pdf
Bertsimas, D., Jaillet, P., Martin, S.: Online vehicle routing: the edge of optimization in large-scale applications. Oper. Res. 67(1), 143–162 (2019). https://doi.org/10.1287/opre.2018.1763
Bischoff, J., Maciejewski, M.: Simulation of city-wide replacement of private cars with autonomous taxis in berlin. In: The 7th International Conference on Ambient Systems, Networks and Technologies, vol. 83, pp. 237–244 (2016)
Braverman, A., Dai, J.G., Liu, X., Ying, L.: Empty-car routing in ridesharing systems. Oper. Res. 67(5), 1437–1452 (2019). https://doi.org/10.1287/opre.2018.1822
Breiman, L.: Random forests. Mach. Learn. 45 (2001)
Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., Juan, A.A.: Rich vehicle routing problem: survey. ACM Comput. Surv. 47(2) (2014). https://doi.org/10.1145/2666003
Dandl, F., Hyland, M., Bogenberger, K., Mahmassani, H.S.: Evaluating the impact of spatio-temporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets. Transportation 46(6), 1975–1996 (2019). https://doi.org/10.1007/s11116-019-10007-9
Fagnant, D.J., Kockelman, K.M.: The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios. Transp. Res. Part C Emerg. Technol. 40, 1–13 (2014). https://doi.org/10.1016/j.trc.2013.12.001
Gendreau, M., Laporte, G., Semet, F.: Solving an ambulance location model by tabu search. Locat. Sci. 5(2), 75–88 (1997). https://doi.org/10.1016/S0966-8349(97)00015-6
Gmira, M., Gendreau, M., Lodi, A., Potvin, J.Y.: Managing in real-time a vehicle routing plan with time-dependent travel times on a road network. Transp. Res. Part C Emerg. Technol. 132, 103379 (2021)
Goldberg, J.B.: Operations research models for the deployment of emergency services vehicles. EMS Manag. J. 1(1), 20–39 (2004)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196–210 (1962). https://doi.org/10.1137/0110015
Ho, S.C., Szeto, W., Kuo, Y.H., Leung, J.M., Petering, M., Tou, T.W.: A survey of dial-a-ride problems: literature review and recent developments. Transp. Res. Part B Methodol. 111, 395–421 (2018)
Holler, J., et al.: Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem. In: 2019 IEEE International Conference on Data Mining (ICDM), pp. 1090–1095. IEEE Computer Society (2019). https://doi.org/10.1109/ICDM.2019.00129
Jiao, Y., et al.: Real-world ride-hailing vehicle repositioning using deep reinforcement learning. Transp. Res. Part C Emerg. Technol. 130, 103289 (2021). https://doi.org/10.1016/j.trc.2021.103289
Jones, E.C., Leibowicz, B.D.: Contributions of shared autonomous vehicles to climate change mitigation. Transp. Res. Part D Transp. Environ. 72, 279–298 (2019). https://doi.org/10.1016/j.trd.2019.05.005
Kaiser, L., et al.: Model-based reinforcement learning for atari. In: International Conference on Learning Representations, ICLR (2020)
Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
Kullman, N.D., Cousineau, M., Goodson, J.C., Mendoza, J.E.: Dynamic ride-hailing with electric vehicles. Transp. Sci. 56(3), 775–794 (2022)
Kumar, S., Panneerselvam, R.: A survey on the vehicle routing problem and its variants. Intell. Inf. Manag. 4(3), 66–74 (2012)
LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. Nature 521, 436–44 (2015). https://doi.org/10.1038/nature14539
Lee, D.H., Wang, H., Cheu, R., Teo, S.H.: Taxi dispatch system based on current demands and real-time traffic conditions. Transp. Res. Rec. 1882, 193–200 (2004). https://doi.org/10.3141/1882-23
Lin, C., Choy, K., Ho, G., Chung, S., Lam, H.: Survey of green vehicle routing problem: past and future trends. Expert Syst. Appl. 41(4, Part 1), 1118–1138 (2014)
Liu, K., Li, X., Zou, C.C., Huang, H., Fu, Y.: Ambulance dispatch via deep reinforcement learning. In: SIGSPATIAL 2020, pp. 123–126. Association for Computing Machinery (2020). https://doi.org/10.1145/3397536.3422204
Luo, Q., Huang, X.: Multi-agent reinforcement learning for empty container repositioning. In: 2018 IEEE 9th International Conference on Software Engineering and Service Science (ICSESS), pp. 337–341 (2018)
Miao, F., et al.: Taxi dispatch with real-time sensing data in metropolitan areas: a receding horizon control approach. IEEE Trans. Autom. Sci. Eng. 13(2), 463–478 (2016). https://doi.org/10.1109/TASE.2016.2529580
Oda, T., Joe-Wong, C.: Movi: a model-free approach to dynamic fleet management. In: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, pp. 2708–2716. IEEE Press (2018). https://doi.org/10.1109/INFOCOM.2018.8485988
Pedregosa, F., et al.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)
Psaraftis, H.N., Wen, M., Kontovas, C.A.: Dynamic vehicle routing problems: three decades and counting. Networks 67(1), 3–31 (2016)
Qiu, X.P., Sun, T.X., Xu, Y.G., Shao, Y.F., Dai, N., Huang, X.J.: Pre-trained models for natural language processing: a survey. Science China Technol. Sci. 63(10), 1872–1897 (2020). https://doi.org/10.1007/s11431-020-1647-3
Riley, C., van Hentenryck, P., Yuan, E.: Real-time dispatching of large-scale ride-sharing systems: integrating optimization, machine learning, and model predictive control. In: IJCAI-20. International Joint Conferences on Artificial Intelligence Organization, pp. 4417–4423 (2020). https://doi.org/10.24963/ijcai.2020/609. Special track on AI for CompSust and Human well-being
Rossi, F., Zhang, R., Hindy, Y., Pavone, M.: Routing autonomous vehicles in congested transportation networks: structural properties and coordination algorithms. Auton. Robot. 42(7), 1427–1442 (2018). https://doi.org/10.1007/s10514-018-9750-5
Seow, K.T., Dang, N.H., Lee, D.H.: A collaborative multiagent taxi-dispatch system. IEEE Trans. Autom. Sci. Eng. 7(3), 607–616 (2010). https://doi.org/10.1109/TASE.2009.2028577
Sermanet, P., Eigen, D., Zhang, X., Mathieu, M., Fergus, R., LeCun, Y.: Overfeat: integrated recognition, localization and detection using convolutional networks (2014)
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2018)
Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization — Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36478-1_17
Xu, Z., et al.: Large-scale order dispatch in on-demand ride-hailing platforms: a learning and planning approach. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 905–913 (2018)
Yuan, E., Chen, W., Van Hentenryck, P.: Reinforcement learning from optimization proxy for ride-hailing vehicle relocation. J. Artif. Intell. Res. (JAIR) 75, 985–1002 (2022). https://doi.org/10.1613/jair.1.13794
Zhang, R., Pavone, M.: Control of robotic mobility-on-demand systems: a queueing-theoretical perspective. Int. J. Robot. Res. 35(1–3), 186–203 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
Appendix 1. Analysis: Features Importance
Features importance.
In addition to the learning-based repositioning strategy, the company is also interested to know which features (time, location, motives, etc.) are the most important to explain a specific decision. To do so, we use permutation feature importance which measures the drop in performance when the dataset is corrupted by randomly shuffling a feature [8]. Figure 5 shows the relative importance of different features for the neural network and the gradient boosting method. The higher the number the more important; the features are grouped by time, PRO, PRA, and prior requests motives. We observe that arrivals (PRA) provide the most information for predictors, as they provide information about the locations of users that might require an additional trip in the future. We confirm these results by training with only parts of the features as shown in Table 5. As suggested by the previous analysis, motives have a small impact on performance, raising the accuracy only by one percent or two, whereas prior requests information is essential to training accurate predictors.
Appendix 2. Analysis: Online Learning
The environment in which our predictor works might vary through changes in request distribution or the way hospitals operates, so it is desirable to be able to adapt the predictor and retrain it on newer and more relevant data. This is commonly referred to as online learning. This can be carried out in several ways, for example, by expanding the training set with new data and retraining the model, or by freezing layers of the model and fitting on the new data. We test the efficiency of retraining approaches.
Our procedure is as follows. The dataset is split into quintiles (groups of 20% of the dataset), and at iteration \(i \in \{1,\dots ,5\}\), the i first quintiles are used to train and the quintile \(i+1\) serves as the test set. This simulates new days of operation as tests, then used to retrain the predictors. This is important for further refining the accuracy of the model, and allows it to adapt to progressive environment changes; Fig. 6 shows how accuracy evolves in time by retraining on all the data available and testing on the subsequent days of operation, averaged over 100 iterations. The quintiles are generated either by shuffling the dataset, or by keeping the data sorted time-wise to replicate retraining in practice. The temporal coherence in small data samples allows the model to capture recent temporal variations in requests but hinders access to a wider selection of examples. Overall, this appears to have a small beneficial impact on the neural network but a negative one for gradient boosting. It is clear that retraining is important for this application when there is relatively little trip data available for initial training.
Retraining accuracy
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Parjadis, A., Cappart, Q., Massoteau, Q., Rousseau, LM. (2023). Repositioning Fleet Vehicles: A Learning Pipeline. In: Sellmann, M., Tierney, K. (eds) Learning and Intelligent Optimization. LION 2023. Lecture Notes in Computer Science, vol 14286. Springer, Cham. https://doi.org/10.1007/978-3-031-44505-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-031-44505-7_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-44504-0
Online ISBN: 978-3-031-44505-7
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science