Loading...

Optimal Vehicle Routing Problem with Pickup and Delivery for Same-Day Delivery Based on Machine Learning Approach

Mehrabi, Mahsa | 2025

1 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: Farsi
  3. Document No: 58883 (01)
  4. University: Sharif University of Technology
  5. Department: Industrial Engineering
  6. Advisor(s): Hassan Nayebi, Erfan
  7. Abstract:
  8. The increasing demand for urban logistics services and the growing customer expectations regarding delivery speed and quality have made the vehicle routing problem a critical operational challenge for logistics companies. In this study, the same-day pickup and delivery vehicle routing problem was investigated using real-world data from a logistics company in Tehran. For this purpose, a mixed integer linear programming model was presented with the aim of minimizing the total travel cost, fixed vehicle operating cost, and delay costs. The problem formulation considered open vehicle routing, pickup and delivery, same-day delivery, stochastic and time-dependent travel times, and heterogeneous fleet characteristics. Since the problem is very large-scale and includes a large number of nodes, computational results demonstrated that solving the integrated problem without decomposition faces serious computational limitations in real-world dimensions, preventing the full definition of decision variables and entry into the optimization stage. To overcome this computational challenge, a two-stage clustering approach was proposed for grouping customer requests. In the first stage, clustering was performed based on spatial features. Six clustering algorithms—hierarchical clustering, DBSCAN, Mean-Shift, Gaussian Mixture Model (GMM), K-Means, and Constrained K-Means—were implemented and compared using performance evaluation indices. Accordingly, the Constrained K-Means algorithm was employed to generate clusters. In the second clustering stage, the resulting clusters were re-clustered using the GMM algorithm based on load characteristics to enable more accurate vehicle-type assignment. Based on the computational results, the problem was further decomposed into smaller subproblems. After forming the final clusters, the routing model was solved independently for each cluster. The results included vehicle-to-cluster assignments, objective function values, delay measures, and the optimal sequence for visiting pickup and delivery nodes. A computational evaluation was conducted by comparing two different request distribution patterns. In the first case, requests were randomly distributed without spatial clustering, whereas in the second case, requests were clustered spatially. The results indicated that clustering requests, due to the spatial proximity of requests, improved objective function by an average of 25.32% and reducing computation time by 92.30%. Overall, the results of the study indicate that the clustering-based problem decomposition approach effectively reduces the computational limitations of the model by transforming the problem into a set of solvable subproblems and enables the extraction of feasible routes and operational assignments in an acceptable time. The proposed framework can be used as a decision-making tool for urban logistics companies and provide a basis for implementing real-scale routing models
  9. Keywords:
  10. Vehicle Routing Problem ; Pickup and Delivery Problem Optimization ; Machine Learning ; Clustering ; Same-Day Delivery

 Digital Object List

 Bookmark

No TOC