Layer: An Alternative Approach To Solve Large Capacitated Vehicle Routing Problem with Time Window Using AI and Exact Method

Mukherjee, Krishnendu (2023): Layer: An Alternative Approach To Solve Large Capacitated Vehicle Routing Problem with Time Window Using AI and Exact Method.

Abstract

To the best of my knowledge, this problem has never been addressed by any researcher. This paper studies the effect of K-means, the Gaussian Mixture Model (GMM), and the integrated use of autoencoder and K-means on the computational time, MIP gap, feasible route, subtour, and the optimum use of vehicles. Miller-Tucker-Zemlin (MTZ) subtour elimination constraint is considered in this regard. This paper also gives the concept of a “layer”, which could be effective to solve a large vehicle routing problem with a time window (VRPTW) quickly.

• Item Type: MPRA Paper
• Language: English
• Keywords: Machine Learning, Deep Learning, Mixed Integer Linear Program, and Large VRPTW
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling

References

1. Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Retrieve from http://cepac.cheme.cmu.edu/pasi2011/library/cerda/braysy-gendreau-vrp-review.pdf

2. Farid Ghannadpour S. and Hooshfar M.(2015). Multi-objective Evolutionary Method for Dynamic Vehicle Routing and Scheduling Problem with Customers’ Satisfaction Level. In Proceedings of the International Conference on Operations Research and Enterprise Systems (ICORES-2015), pages 91-98.DOI: 10.5220/0005172600910098

3. M. Barkaoui , J. Berger , A. Boukhtouta (2015). Customer satisfaction in dynamic vehicle routing problem with time windows, Applied Soft Computing, Vol. 35, pp.423-432.

4. Nathalie De Jaegere, Mieke Defraeyea and Inneke Van Nieuwenhuyse (2014). The Vehicle Routing Problem: State of the Art Classification and Review. Retrieved from https://core.ac.uk/download/pdf/34605432.pdf

5. Jing Fang (2011). The Vehicle Routing Problem with Simultaneous Pickup and Delivery Based on Customer Satisfaction, Vol.15, pp. 5284-5289.

6. Mehmet Fatih Yüce, Ali Gunes, Metin Zontul, Tuğba Altintas. Time Window and Location Based Clustered Routing with Big and Distributed Data. Industrial Engineering. Vol. 2, No. 2, 2018, pp. 42-51. doi: 10.11648/j.ie.20180202.11

7. Serap Ercan Cӧmert, Harun Reᶊit Yazgan, Irem Sertvuran and Hanife Șengȕl (2017). A n e w approach for solution of vehicle routing problem with hard time window : an application in a super market chain, Sadhana, Vol. 42, No. 12, pp. 2067–2080.

8. Ropke, Stefan, and David Pisinger. 2006. “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows.” Transportation Science 40 (4): 455–472.

9. Bai, Ruibin, Edmund K. Burke, Michel Gendreau, Graham Kendall, and Barry McCollum. 2007. Memory length in hyper-heuristics: An empirical study. New York: IEEE.

10. Hanjun Dai, Bo Dai, and Le Song. “Discriminative Embeddings of Latent Variable Models for Structured Data”. In: Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48. ICML’16. New York, NY, USA: JMLR.org, 2016, pp. 2702–2711.

11. Mohammadreza Nazari et al. Reinforcement Learning for Solving the Vehicle Routing Problem. 2018. arXiv: 1802.04240 [cs.AI].

12. Hottung, André, and Kevin Tierney. 2019. “Neural large neighborhood search for the capacitated vehicle routing problem.” In arXiv, https://arxiv.org/abs/1911.09539.

13. Wouter Kool, Herke van Hoof, and Max Welling. “Attention, Learn to Solve Routing Problems!” In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.

14. Maryam Abdirad & Krishna Krishnan. Industry 4.0 in Logistics and Supply Chain Management: A Systematic Literature Review, Engineering Management Journal,2020.

15. Battarra, M., Erdoğan, G., and Vigo, D., Exact Algorithms for the Clustered Vehicle Routing Problem, Operations Research.

16. Barreto, S., Ferreira, S., Paixão, J., and Santos, S. B. Using clustering analysis in a capacitated location-routing problem, European Journal of Operational Research, Vol.179, pp. 968-977,2007.

17. Alesiani, F., Ermis, G., and Gkiotsalitis, K. Constrained Clustering for the Capacitated Vehicle Routing Problem (CC-CVRP), Applied Artificial Intelligence, Vol.36,No.1, 2022.

18. Abbas, F., and Fan,P. Clustering-based reliable low-latency routing scheme using ACO method for vehicular networks, Vehicular Communications,Vol.12, pp.66-74,2018.

19. Song, C., Liu, F., Huang, Y., Wang,L., and Tan, T. Auto-encoder Based Data Clustering,2013.

20. Sahal, R., Breslin, J.G., Ali, M.,I. (2020) Big data and stream processing platforms for Industry 4.0 requirements mapping for a predictive maintenance use case, Journal of Manufacturing Systems, Vol.54,pp.138-151.

21. Bellavista, P., Bosi, F., Corradi, A., Foschini,L., Monti, S., Patera, L., Poli, L., Scotece,D., and Solimando, M. (2019) Design Guidelines for Big Data Gathering in Industry 4.0 Environments.

22. Peres, R.S., Rocha, A.D., Coelho, A., and Barata, J. A Highly Flexible, Distributed Data Analysis Framework for Industry 4.0 Manufacturing Systems.

23. Gareth, J., Witten, D., Hastie, T., and Tibshirani, R. (2017) An Introduction to Statistical Learning with Applications in R, ISBN 978-1-4614-7138-7 (eBook).

24. Nasiriany, S., Thomas, G., Wang, W., Yang, A., Listgarten, J., Sahai, A. (2019) A Comprehensive Guide to Machine Learning. 25. Murphy, K.P. (2012) Machine Learning A Probabilistic Perspective, MIT Press, England.

26. Quintiq. (2015). https://www.sintef.no/contentassets/51a833740c45438b99b2935fd1c057d1/c1_10_1.42478.95.sintef.txt