Machine learning based route optimization for the travelling salesman problem with pickup and delivery

• Main Author: Ong, Zhi Ying
• Format: Final Year Project / Dissertation / Thesis
• Published: 2023
• Subjects: QA76 Computer software
• Online Access: http://eprints.utar.edu.my/5887/1/SE_1903193_FYP_report_%2D_OngZhiYing_%2D_ZHI_YING_ONG.pdf; http://eprints.utar.edu.my/5887/
• Institution: Universiti Tunku Abdul Rahman

The booming of online consumers has resulted in the strong demand of ecommerce postal delivery services. To gain the competitive advantages among other couriers, most couriers try their best to offer their customers effective pickup and delivery services with short delivery time. The customers refer to retailers or purchasers or both. In this context, the travelling salesman problem can be applied. This project aims to achieve the shortest Estimated Time of Arrival (ETA) that allows couriers to collect goods from every customer's location exactly once and returns to the original travelling point. However, there is a high possibility for a courier to visit a customer's location multiple times if the customer happens to be the seller and the buyer at the same time. Consequently, the courier cost will increase, which leads to in low customer satisfaction due to long pickup and delivery time, particularly during peak hours. The goal of this project is to deliver an optimal route for pickup and delivery using Reinforcement Learning (RL) and Genetic Algorithm (GA). 16 locations in Klang Valley are chosen randomly and later ETAs between them are retrieved for testing purpose. It is found that GA is better than RL in finding optimal route.