A clustering algorithm for solving the vehicle routing assignment problem in polynomial time

  • Authors

    • L. W. Rizkallah Computer Engineering dept, Cairo University
    • M. F. Ahmed Computer Engineering dept, Cairo University
    • N. M. Darwish Computer Engineering dept, Cairo University
    2020-01-11
    https://doi.org/10.14419/ijet.v9i1.22231
  • Agglomerative Hierarchical Clustering, Clarke and Wright Saving Method, Clustering Algorithms, Solomon’s Benchmarks, Vehicle Routing Problems.

  • The Vehicle Routing Problem (VRP) consists of a group of customers that needs to be served. Each customer has a certain demand of goods. A central depot having a fleet of vehicles is responsible for supplying the customers with their demands. The problem is composed of two sub-problems: The first sub-problem is an assignment problem where both the vehicles that will be used as well as the customers assigned to each vehicle are determined. The second sub-problem is the routing problem in which for each vehicle having a number of cus-tomers assigned to it, the order of visits of the customers is determined. Optimal number of vehicles as well as optimal total distance should be achieved. In this paper, an approach for solving the first sub-problem, the assignment problem, is presented. In the approach, a clustering algorithm is proposed for finding the optimal number of vehicles by grouping the customers into clusters where each cluster is visited by one vehicle. This work presents a polynomial time clustering algorithm for finding the optimal number of clusters. Also, a solution to the assignment problem is provided. The proposed approach was evaluated using Solomon’s C1 benchmarks where it reached optimal number of clusters for all the benchmarks in this category. The proposed approach succeeds in solving the assignment problem in VRP achieving a solving time that surpasses the state-of-the-art approaches provided in the literature. It also provides a means of working with varying num-ber of customers without major increase in solving time.

     

     

  • References

    1. [1] Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N. and Rei, W., 2012. "A Hybrid Genetic Algorithm for Multi-Depot and Periodic Vehicle Routing Problems", Operations Research, Vol. 60(3), pp. 611-624. https://doi.org/10.1287/opre.1120.1048.

      [2] Fukasawa, R., Longo, H., Lysgaard, J., Poggi de Aragão, M., Reis, M., Uchoa, E. and Werneck, R. F., 2006. "Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem", Mathematical Programming, Vol. 106(3), pp. 491-511. https://doi.org/10.1007/s10107-005-0644-x.

      [3] Lysgaard, J., Letchford, A.N. and Eglese, R.W., 2004. "A New Branch-and-Cut Algorithm for Capacitated Vehicle Routing Problems", Mathematical Programming, Series A, Vol. 100, pp. 423-445. https://doi.org/10.1007/s10107-003-0481-8.

      [4] Dhahri, A., Zidi, K. and Ghedira, K., 2014. "Variable Neighborhood Search Based Set Covering ILP Model for the Vehicle Routing Problem with Time Windows", Procedia Computer Science, Vol. 29, PP. 844–854. https://doi.org/10.1016/j.procs.2014.05.076.

      [5] Hong L., 2012. "An Improved LNS Algorithm for Real-Time Vehicle Routing Problem with Time Windows", Comput Oper Res, Vol. 39(2), pp. 151–163. https://doi.org/10.1016/j.cor.2011.03.006.

      [6] Pichpibul, Tantikorn and Kawtummachai, R., 2012. "An Improved Clarke and Wright Savings Algorithm for the Capacitated Vehicle Routing Problem", Science Asia, Vol. 38(3), pp. 307-318. https://doi.org/10.2306/scienceasia1513-1874.2012.38.307.

      [7] Akeb, Hakim, Bouchakhchoukha, A. and Hifi, M., 2015. "A Three-Stage Heuristic for the Capacitated Vehicle Routing Problem with Time Windows", Recent Advances in Computational Optimization, Vol. 580, pp. 1-19. https://doi.org/10.1007/978-3-319-12631-9_1.

      [8] Cordeau, J. F., Laporte, G. and Mercier, A., 2011. "A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows", Journal of the Operational Research Society, Vol. 52, pp. 928-936. https://doi.org/10.1057/palgrave.jors.2601163.

      [9] Bent, R.,Van and Hentenryck, P., 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows", Transp Sci, Vol. 38(4), pp. 515–530. https://doi.org/10.1287/trsc.1030.0049.

      [10] Nagata Y., Bräysy O. and Dullaert W., 2010. "A Penalty-Based Edge Assembly Memetic Algorithm for the Vehicle Routing Problem with Time Windows", Comput Oper Res, Vol. 37(4), pp. 724–737. https://doi.org/10.1016/j.cor.2009.06.022.

      [11] Nagata, Yuichi and Bräysy, O., 2009. "A powerful Route Minimization Heuristic for the Vehicle Routing Problem with Time Windows", Operations Research Letters, Vol. 37(5), pp. 333-338. https://doi.org/10.1016/j.orl.2009.04.006.

      [12] Wenbin, H., 2013. "A Hybrid Chaos-Particle Swarm Optimization Algorithm for the Vehicle Routing Problem with Time Window", Entropy, Vol. 15(4), pp. 1247-1270. https://doi.org/10.3390/e15041247.

      [13] Ruey-Maw, C., Hsieh, F., and Di-Shiun, W., 2012. "Heuristics Based Ant Colony Optimization for Vehicle Routing Problem", Industrial Electronics and Applications (ICIEA), 2012 7th IEEE Conference.

      [14] Jun, J., 2014. "Vehicle Routing Problem with a Heterogeneous Fleet and Time Windows", Expert Systems with Applications, Vol. 41(8), pp. 3748-3760. https://doi.org/10.1016/j.eswa.2013.11.029.

      [15] Prescott-Gagnon, E., Desaulniers, G., and Rousseau, L.-M., 2009. "A branch-and-Price Based Large Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows", Networks, Vol. 54(4), pp. 190-204. https://doi.org/10.1002/net.20332.

      [16] Mahmoudi, Monirehalsadat, and Zhou, X., 2016. "Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows: A Dynamic Programming Approach Based on State–Space–Time Network Representations", Transportation Research, Part B: Methodological, Vol. 89, pp. 19-42. https://doi.org/10.1016/j.trb.2016.03.009.

      [17] Diego, P., 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows", INFORMS Journal on Computing, Vol. 29(3), pp. 489-502. https://doi.org/10.1287/ijoc.2016.0744.

      [18] Everitt, B. S., Landau, S., Leese, M., and Stahl, D., 2011. "Hierarchical Clustering", In: Cluster Analysis, 5th ed., John Wiley & Sons Ltd, Chichester, UK. https://doi.org/10.1002/9780470977811.

      [19] Madhulatha TS., 2012. "An overview on Clustering Methods", Journal of Engineering arXiv: 1205.1117., Vol. 2(4), pp. 719-725. https://doi.org/10.9790/3021-0204719725.

      [20] Kriegel HP, Kröger P., Sander J., and Zimek A., 2011. "Densityâ€Based Clustering", Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, Vol. 1(3), pp. 231-240. https://doi.org/10.1002/widm.30.

      [21] Bouveyron, Charles, and Brunet-Saumard, C., 2014. "Model-Based Clustering of High-Dimensional Data: A Review", Computational Statistics & Data Analysis, Vol. 71, pp. 52-78. https://doi.org/10.1016/j.csda.2012.12.008.

      [22] Pradeep, R., Singh, S., 2010. "A Survey of Clustering Techniques", International Journal of Computer Applications, Vol. 7(12), pp. 1-5. https://doi.org/10.5120/1326-1808.

      [23] Hruschka, E., Carlos, S., Campello, R., Freitas, A., and De Carvalho, A., 2009. "A Survey of Evolutionary Algorithms for Clustering. Systems", Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions, Vol. 39(2), pp. 133-155. https://doi.org/10.1109/TSMCC.2008.2007252.

      [24] Barnhart, Cynthia, Laporte, G., 2006. "Handbooks in Operations Research & Management Science", Transportation, Vol. 14, pp. 367-417.

      [25] Caccetta, Louis, Alameen, M., and Abdul-Niby, M., 2013. "An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem", Engineering, Technology & Applied Science Research, Vol. 3(2), pp. 413.

      [26] Vehicle Routing Problem. [Internet]. Spain: University of Malaga [updated 2013 Jan 7; cited 2016 May 18]. Available from: http://neo.lcc.uma.es/vrp/

      [27] Solomon Benchmarks. [Internet]. Norway: Company of Scientific and Industrial Research at the Norwegian Institute of Technology [updated 2008 April 18; cited 2016 May 18]. Available from: https://www.sintef.no/projectweb/top/vrptw/solomon-benchmark.

      [28] Shin, K., & Han, S. (2012). A centroid-based heuristic algorithm for the capacitated vehicle routing problem. Computing and Informatics, 30(4), 721-732.

      [29] Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations research, 40(2), 342-354. https://doi.org/10.1287/opre.40.2.342.

  • Downloads

  • How to Cite

    W. Rizkallah, L., F. Ahmed, M., & M. Darwish, N. (2020). A clustering algorithm for solving the vehicle routing assignment problem in polynomial time. International Journal of Engineering & Technology, 9(1), 1-8. https://doi.org/10.14419/ijet.v9i1.22231