Proposed Modified Clarke-Wright Saving Algorithm for Capacitated Vehicle Routing Problem
DOI:
https://doi.org/10.24002/ijieem.v1i1.2292Keywords:
Clarke-Wright saving matrix, capacitated vehicle routing problem, optimization, traveling time.Abstract
A multi-objective distribution routing algorithm by using modified Clarke and Wright Saving algorithm is presented. The problem to solve is to deliver loads to a number of outlets based load requirement. The objective function to minimize is the distance saving and traveling time of the resulted route started from depot to the outlets and return to the original depot. Problem to solve is generating a distribution route in a week considering traffic condition for each day. The original Clarke and Wright saving algorithm is modified such that the resulted routes (from a depot to some outlets) accommodates some constraints such as the maximum allowable traveling time, maximum number of delivery shifts, and maximum number of vehicles. The algorithm is applied to a distributor company with nine outlets, two vehicles, and two delivery shifts. In addition, the traffic condition on the outlet-to-outlet and the depot-to-outlet routes is considered. The simulation of the proposed algorithm shows that the algorithm can generate routes that comply with shift’s maximum delivery time and the vehicles’ capacities.
References
Bae, H. and Moon, I. (2016). Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles. Applied Mathematical Modelling, 40(13-14), 6536-6549.
Baniamerian, A., Bashiri, M., and Zabihi, F. (2017). Two phase genetic algorithm for vehicle routing and scheduling problem with cross-docking and time windows considering customer satisfaction. Journal of Industrial Engineering International, 14(1), 15-30.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of
delivery points. Operations Research, 12(4), 568-582.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–92.
Hu, H., Li. X., Zhang, Y., Shang, C., and Zhang, S. (2019). Multi-objective location-routing model for hazardous material logistics with traffic restriction constraint in inter-city roads. Computer & Industrial Engineering, 128, 861-876.
Li, H., Lv, T., and Li, Y. (2015). The tractor and semitrailer routing problem with many-to-many demand considering carbon dioxide emissions. Transportation Research Part D, 34, 68-82.
Li, H., Zhang, L., Ly, T., and Chang, X. (2016). The two-echelon time constrained vehicle routing problem in linehaul-delivery systems.
Matos, M. R. S., Frota, Y., and Ochi, L. S. (2018). Green vehicle routing and scheduling problem with split delivery. Electronic Notes in Discrete Mathematics, 69, 13-20.
Pichpibul, T. and Kawtummachai, R. (2013). A heuristic approach based on Clarke-Wright algorithm for open vehicle routing problem. The Scientific World Journal, 11 (ID: 874349), 1-11.
Sabar, N. R., Bhaskar, A., Chung, E., Turky, A., and Andy Song. (2019). A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion. Swarm and Evolutionary Computation, 44, 1018-1027.
Xiao, Y. and Konak A. (2016). The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transportation Research Part E, 88, 146-166.
Downloads
Published
How to Cite
Issue
Section
License
The copyright of the received article shall be assigned to the journal as the publisher of the journal. The intended copyright includes the right to publish the article in various forms (including reprints). The journal maintains the publishing rights to the published articles.
This work is licensed under a Creative Commons Attribution 4.0 International License