Proposed Modified Clarke-Wright Saving Algorithm for Capacitated Vehicle Routing Problem

A.K. Pamosoaji, P.K. Dewa, J.V. Krisnanta

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.

 


Keywords


Clarke-Wright saving matrix, capacitated vehicle routing problem, optimization, traveling time.

Full Text:

PDF

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.




DOI: https://doi.org/10.24002/ijieem.v1i1.2292

Refbacks

  • There are currently no refbacks.