Developing and Assessing New Models for the Free Patrol Vehicle Routing Problem

Document Type : Article

Authors

School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Abstract

Vehicle routing problems are a category of complex mathematical problems in the field of transportation and supply chain management, and a wide variety of these problems have been introduced. One category within this field involves the collaboration of two different types of fleets in a network, where in many cases, one of the fleets must patrol the graph as a support fleet and is not subject to the same constraints as the other fleet, such as only visiting a vertex or an edge once. Examples include refueling fleets or trucks providing services to drones, where these fleets patrol the network so that the other fleet can use their services as needed.
In this paper, the problem of the free movement of such fleets on a graph is examined as a free patrol problem, which can be used as a sub-problem in the modeling and solving of many routing problems. To this end, the problem is modeled as a mixed-integer linear programming (MILP) problem in both discrete and continuous time spaces. Generally, it is expected that the model in continuous time space will exhibit lower computational complexity, but since modeling in continuous time requires changes to the graph, leading to an increase in the number of vertices and edges, its behavior needs to be more thoroughly investigated. On the other hand, another challenge in analyzing this problem is that the objective of the free patrol sub-problem depends on the main problem, as without the main problem, the free patrol problem may lose its objective, with a fleet patrolling the graph within a designated time. Therefore, to decouple and make the free patrol independent of the main problem, five different objective functions have been introduced for each model, covering a wider range of comparisons, leading to ten models in total. Subsequently, all ten models were solved exactly using randomly generated data for ten different graphs. Finally, the behavior of the models was evaluated and compared from various perspectives. The numerical results demonstrate the superior performance of the continuous time model over the discrete time model.

Keywords

Main Subjects

References

1. Manshadian, H., Amalnick, M. S. and Torabi, S. A., 2023. Synchronized truck and drone routing under disastrous conditions (case study: urban thoroughfares disinfection). Computers & Operations Research, 106295. https://doi.org/10.1016/j.cor.2023.106295
2. Schrijver, A., 2005. On the history of combinatorial optimization (till 1960). Handbooks in operations research and management science, 12, pp. 1-68. https://doi.org/10.1016/S0927-0507(05)12001-5
3. Xing, Z., Tu, S. and Xu, L., 2020. Solve Traveling Salesman Problem by Monte Carlo Tree Search and Deep Neural Network. arXiv preprint arXiv:2005.06879. https://doi.org/10.48550/arXiv.2005.06879
4. Zhou, A.-H., Zhu, L.-P., Hu, B., Deng, S., Song, Y., Qiu, H. and Pan, S., 2019. Traveling-salesman-problem algorithm based on simulated annealing and gene-expression programming. Information, 10, 7. https://doi.org/10.3390/info10010007
5. Ahmed, Z. H., 2020. Adaptive Sequential Constructive Crossover Operator in a Genetic Algorithm for Solving the Traveling Salesman Problem. GAs, 11. https://dx.doi.org/10.14569/IJACSA.2020.0110275
6. Guo, J. and Sato, Y., 2020. A Standardized Bare Bones Particle Swarm Optimization Algorithm for Traveling Salesman Problem. International Journal of Machine Learning and Computing, https://doi.org/10.18178/ijmlc.2020.10.3.960
7. Dahan, F., El Hindi, K., Mathkour, H. and Alsalman, H., 2019. Dynamic flying ant colony optimization (DFACO) for solving the traveling salesman problem. Sensors, 19, 1837. https://doi.org/10.3390/s19081837
8. Dror, M., 2012. Arc routing: theory, solutions and applications, Springer Science & Business Media. https://doi.org/10.1007/978-1-4615-4495-1
9. Eiselt, H. A., Gendreau, M. and Laporte, G., 1995. Arc routing problems, part II: The rural postman problem. Operations research, 43, pp. 399-414. https://doi.org/10.1287/opre.43.3.399
10. Assad, A. A. and Golden, B. L., 1995. Arc routing methods and applications. Handbooks in operations research and management science, 8, pp. 375-483. https://doi.org/10.1016/S0927-0507(05)80109-4
11. Yu, M., Jin, X., Zhang, Z., Qin, H. and Lai, Q., 2019. The split-delivery mixed capacitated arc-routing problem: Applications and a forest-based tabu search approach. Transportation Research Part E: Logistics and Transportation Review, 132, pp. 141-162. https://doi.org/10.1016/j.tre.2019.09.017
12. Corberán, Á., Erdoğan, G., Laporte, G., Plana, I. and Sanchis, J. M., 2018. The Chinese Postman Problem with load-dependent costs. Transportation Science, 52, pp. 370-385. https://doi.org/10.1287/trsc.2017.0774
13. Christofides, N., Benavent, E., Campos, V., Corberán, A. and MOTA, E., 1984. An optimal method for the mixed postman problem. System modelling and optimization. Springer. https://doi.org/10.1007/BFb0008937
14. Minieka, E., 1979. The Chinese postman problem for mixed networks. Management Science, 25, pp. 643-648. https://doi.org/10.1287/mnsc.25.7.643
15. Dror, M., Stern, H. and Trudeau, P., 1987. Postman tour on a graph with precedence relation on arcs. Networks, 17, pp. 283-294. https://doi.org/10.1002/net.3230170304
16. Orloff, C., 1974. A fundamental problem in vehicle routing. Networks, 4, pp. 35-64. https://doi.org/10.1002/net.3230040105
17. Lenstra, J. K. and Kan, A. R., 1976. On general routing problems. Networks, 6, pp. 273-280. https://doi.org/10.1002/net.3230060305
18. Hertz, A., Laporte, G. and Hugo, P. N., 1999. Improvement procedures for the undirected rural postman problem. INFORMS Journal on computing, 11, pp. 53-62. https://doi.org/10.1287/ijoc.11.1.53
19. Christofides, N., Campos, V., Corberán, A. and Mota, E., 1986. An algorithm for the rural postman problem on a directed graph. Netflow at pisa. Springer. https://doi.org/10.1007/BFb0121091
20. Corberán, Á., Plana, I. and Sanchis, J. M., 2014. The rural postman problem on directed, mixed, and windy graphs. Arc Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization, pp. 101-127. https://doi.org/10.1137/1.9781611973679.ch6
21. Golden, B. L. and Wong, R. T., 1981. Capacitated arc routing problems. Networks, 11, pp. 305-315. https://doi.org/10.1002/net.3230110308
22. Elshaer, R. & AWAD, H., 2020. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers & Industrial Engineering, 140, 106242. https://doi.org/10.1016/j.cie.2019.106242
23. Konstantakopoulos, G. D., Gayialis, S. P. and Kechagias, E. P., 2020. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational research, pp. 1-30. https://doi.org/10.1007/s12351-020-00600-7
24. Moghdani, R., Salimifard, K., Demir, E. and Benyettou, A., 2021. The green vehicle routing problem: A systematic literature review. Journal of Cleaner Production, 279, 123691. https://doi.org/10.1016/j.jclepro.2020.123691
25. Raeesi, R. and Zografos, K. G., 2020. The electric vehicle routing problem with time windows and synchronised mobile battery swapping. Transportation Research Part B: Methodological, 140, pp. 101-129. https://doi.org/10.1016/j.trb.2020.06.012
26. Wang, Z. and Sheu, J.-B., 2019. Vehicle routing problem with drones. Transportation research part B: methodological, 122, pp. 350-364. https://doi.org/10.1016/j.trb.2019.03.005
27. Chung, S. H., Sah, B. and Lee, J., 2020. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Computers & Operations Research, 123, 105004. https://doi.org/10.1016/j.cor.2020.105004
28. Drexl, M., 2012. Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints. Transportation Science, 46, pp. 297-316. https://doi.org/10.1287/trsc.1110.0400
29. Fleischmann, B., 1990. The vehicle routing problem with multiple use of vehicles. Forschungsbericht Fachbereich Wirtschaftswissenschaften, Universität Hamburg. https://www.researchgate.net/publication/221704650_The_vehicle_routing_problem_with_multiple_use_of_vehicles
 
Sharif Journal of Industrial Engineering & Management
Volume 41, Issue 1 - Serial Number 1
September 2025
Pages 98-108

Files

Share

How to cite

Statistics