An Ant Colony Optimization Heuristic to solve the VRP with Time Window


The KIPS Transactions:PartB , Vol. 17, No. 5, pp. 389-398, Oct. 2010
10.3745/KIPSTB.2010.17.5.389,   PDF Download:

Abstract

The Vehicle Routing and Scheduling Problem with Time Windows(VRSPTW) is to establish a delivery route of minimum cost satisfying the time constraints and capacity demands of many customers. The VRSPTW takes a long time to generate a solution because this is a NP-hard problem. To generate the nearest optimal solution within a reasonable time, we propose the heuristic by using an ACO(Ant Colony Optimization) with multi-cost functions. The multi-cost functions can generate a feasible initial-route by applying various weight values, such as distance, demand, angle and time window, to the cost factors when each ant evaluates the cost to move to the next customer node. Our experimental results show that our heuristic can generate the nearest optimal solution more efficiently than Solomon I1 heuristic or Hybrid heuristic applied by the opportunity time.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
M. D. Hong, Y. H. Yu, G. S. Jo, "An Ant Colony Optimization Heuristic to solve the VRP with Time Window," The KIPS Transactions:PartB , vol. 17, no. 5, pp. 389-398, 2010. DOI: 10.3745/KIPSTB.2010.17.5.389.

[ACM Style]
Myung Duk Hong, Young Hoon Yu, and Gen Sik Jo. 2010. An Ant Colony Optimization Heuristic to solve the VRP with Time Window. The KIPS Transactions:PartB , 17, 5, (2010), 389-398. DOI: 10.3745/KIPSTB.2010.17.5.389.