Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1324399082.pdf (1.85 MB)

ETD Abstract Container

Abstract Header

Ant Colony Optimization Technique to Solve Min-Max MultiDepot Vehicle Routing Problem

Venkata Narasimha, Koushik Srinath
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1324399082

Abstract Details

2011, MS, University of Cincinnati, Engineering and Applied Science: Mechanical Engineering.
This research focuses on solving the min-max Multi Depot Vehicle Routing Problem (MDVRP) based on a swarm intelligence based algorithm called ant colony optimization. A traditional MDVRP tries to minimize the total distance travelled by all the vehicles to all customer locations. The min-max MDVRP, on the other hand, tries to minimize the maximum distance travelled by any vehicle. The algorithm developed is an extension of Single Depot Vehicle Routing Problem (SDVRP) algorithm developed by Bullnheimer et al. in 1997 based upon ant colony optimization. In SDVRP, all the vehicles start from a single depot and return to the same depot, and solution aims at finding tours of vehicles so that every customer location is visited exactly once and that minimizes the total distance travelled. Building upon the SDVRP algorithm, this study first involves developing an algorithm for the min-max variant of SDVRP problem where the maximum distance travelled by any vehicle is minimized. Later, the algorithm has been extended to address the Multi Depot variant of this problem. In this case, vehicles can start from multiple depots unlike SDVRP case and have to come back to their respective depot of origin once they visit a set of customer locations. The min-max multi-depot vehicle routing problem involves minimizing the maximum distance travelled by any vehicle in case of vehicles starting from multiple depots and travelling to each customer location at least once. This problem is of specific significance in case of time critical applications such as emergency response in large-scale disasters, and server-client network latency. The proposed algorithm uses an equitable region partitioning approach aimed at assigning customer locations to depots so that MDVRP is reduced to SDVRP. A background study on swarm intelligence based optimization techniques, region partitioning methods, approximation algorithms and also various techniques of optimization has been included in this research. The proposed method has been implemented in Matlab for obtaining the solution for the min-max MDVRP with any number of vehicles and customer locations. A comparative study is carried out to evaluate the proposed algorithm’s performance with respect to a currently available algorithm in literature in terms of the optimality of solution and time taken to reach the solution. Based on an extensive simulation study, it has been demonstrated that the ant colony optimization technique proposed in this thesis leads to more optimal results as compared to an existing method.
Manish Kumar, PhD (Committee Chair)
Sundararaman Anand, PhD (Committee Member)
Kelly Cohen, PhD (Committee Member)
69 p.
Mechanics
Ant Colony Optimization; Min-Max Multi Depot Vehicle Routing Problem; Optimization Techniques; Vehicle Routing Problem; Min-Max Single Depot Vehicle Routing Problem; Combinatorial Optimization Problems;

Recommended Citations

Citations

  • Venkata Narasimha, K. S. (2011). Ant Colony Optimization Technique to Solve Min-Max MultiDepot Vehicle Routing Problem [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1324399082

    APA Style (7th edition)

  • Venkata Narasimha, Koushik Srinath. Ant Colony Optimization Technique to Solve Min-Max MultiDepot Vehicle Routing Problem. 2011. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1324399082.

    MLA Style (8th edition)

  • Venkata Narasimha, Koushik Srinath. "Ant Colony Optimization Technique to Solve Min-Max MultiDepot Vehicle Routing Problem." Master's thesis, University of Cincinnati, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1324399082

    Chicago Manual of Style (17th edition)

ucin1324399082
2,375
© 2011, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.