Abstract

Regarding the scheduling problem of the trucks which collects municipal solid waste, a major concern to the municipal administrators is how to effectively distribute collection vehicles and crews in the region. Vehicle Routing Problem (VRP) deals with the problem of allocating trucks to the waste collection sites with minimum cost. There were many studies and methods for the determination of the optimal vehicle routing for solid waste collection. Depending on the complexity of the model, exact and heuristic methods have been developed. One of the best-known approach to VRP is the "savings" algorithm of Clarke and Wright[4]. In this paper, we formulate a weighted-graph model of the VRP and analyze worst-case algorithmic complexity of the Clarke-Wright algorithm to determine optimal routes which allow minimizing total distance traversed, total rounds duration and financial costs including salary, fuel and vehicle operation. Also, some practical infeasibility of Clarke-Wright algorithm is pointed out and better alternate, simple graph-based algorithm for VRP is suggested.

Keywords

References

[1] Truitt, M., Liebman, J., Kruse, C., 1969. Simulation model of urban refuse collection. Journal of theSanitary Engineering Division, 289–298.
[2] Armstrong, J.M., Khan, A.M., 2004. Modeling urban transportation emissions: role of GIS. Computers,Environment and Urban Systems 28, 421–433.
[3] Lopez Alvarez, J.V., Aguilar Larrucea, M., Fernandez-Carrion Quero, S., Jimenez del Valle, A., 2008.Optimizing the collection of used paper from small businesses through GIS techniques: Legane´scase (Madrid, Spain). Waste Manage. 28, 282–293.
[4] Clarke, G. & Wright, J.W.: "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research, Vol. 12, 1964, pp. 568-581.
[5] Vehicle Routing Efficiency-Comparison of districting method & Clarke-Wright method, American Journal of Agricultural Economics, Vol. 62, No. 3 (Aug., 1980), pp 534-536.
[6] Danijelmarković, dragoslavjanošević, miomirjovanović, Vesnanikolić, Application method for optimization in solid Waste management system in the city of NIŠ, FactauniversitatisSeries: Mechanical Engineering vol. 8, no 1, 2010, pp. 63 – 76.
[7] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
[8] Frank Harary, Graph Theory, Narosa Publishers, 1996.