Optimizing Dead Mileage in Urban Bus Routes. Dakar Dem Dikk Case Study

Cheikh B. Djiba, Mamadou Balde, Babacar M. Ndiaye, Roger M. Faye, Diaraf Seck

Laboratory of Information Processing, ESP Dakar, Cheikh Anta Diop University, BP: 5085 Dakar, Senegal.
Laboratory of Mathematics of Decision and Numerical Analysis, FASEG, Cheikh Anta Diop University, BP: 45087 Dakar-Fann, Dakar, Senegal.
Unit Mixte Internationale, Ummisco, Institut de Recherche pour le Dveloppement, Bondy, France.

DOI: 10.4236/jtts.2012.23026                

Abstract

This paper studies the buses assignment from their depots to their routes starting points in urban transportation network. It describes a computational study to solve the dead mileage minimization to optimality. The objective of this work is to assign the buses to depots while optimizing dead mileage associated with pull-out trips and pull-in trips. To do so, a new mixed-integer programming model with 0 - 1 variables is proposed which takes into account the specificity of the buses of Dakar Dem Dikk (the main public transportation company in Dakar). This company manages a fleet of buses which, depending on road conditions some buses cannot circulate on some roads of the network. Thus, buses are classified into two categories and are assigned based on these categories. The related mixed-integer 0 - 1 linear program is solved efficiently to minimize the cumulative distance covered by all buses. Numerical simulations on real datasets are presented.

Keywords

Global Optimization; Dead Mileage; Assignment; Urban Transportation Twocolumnfalse

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	F. F. Boctor, J. Renaud and S. Bournival, “Choix de Sites D’Entrep?ts Pour Les Autobus de Transport Urbain: Le Cas du Réseau de Transport de La Capitale,” 2006. http://www.fsa.ulaval.ca/personnel/renaudj/pdf/Recherche/RTC%20INFOR.pdf
[2]	J. A. Hsu, “Discussion on the Paper: Optimizing Dead Mileage in Urban Bus Routes,” Journal of Transportation Engineering, Vol. 114, No. 1, 1988, pp. 123-125. doi:10.1061/(ASCE)0733-947X(1988)114:1(123)
[3]	S. Prakash, B. V. Balaji and D. Tuteja, “Optimizing Dead Mileage in Urban Bus Routes through a Nondominated Solution Approach,” European Journal of Operational Research, Vol. 114, No. 3, 1999, pp. 465-473. doi:10.1016/S0377-2217(98)00238-0
[4]	V. Sharma and S. Prakash, “Optimizing Dead Mileage in Urban Bus Routes,” Journal of Transportation Engineering, Vol. 112, No. 1, 1986, pp. 121-129. doi:10.1061/(ASCE)0733-947X(1986)112:1(121)
[5]	H. S. Kasana and K. D. Kumar, “An Efficient Algorithm for Multiobjective Transportation Problems,” Asia-Pacific Journal of Operational Research, Vol. 17, 2000, pp. 27-40.
[6]	A. K. Agrawal and S. L. Dhingra, “An Optimal Program for Augmentation of Capacities of Depots and Shipment of Buses from Depots to Starting Points of Routes,” Indian Journal of Pure and Applied Mathematics, Vol. 20, No. 2, 1989, pp. 111-120.
[7]	S. Prakash and V. Saini, “Selection of Optimal Site for New Depot of Specified Capacity with Two Objectives,” Indian Journal of Pure and Applied Mathematics, Vol. 20, No. 5, 1989, pp. 425432.
[8]	A. S. Pepin, G. Desaulniers and A. Hertz, “Comparison of Heuristic Approaches for the Multiple Depot Vehicle Scheduling Problem,” Les Cahiers du GERAD, Vol. 65, 2006.
[9]	C. B. Djiba, “Optimal Assignment of Routes to a Terminal for an Urban Transport Network. Master of Research Engineering Sciences,” Cheikh Anta Diop University, 2008.
[10]	Full Traffic of Dakar Dem Dikk (2008-2009), InputOutput File. http://www.demdikk.com
[11]	IBM ILOG CPLEX Optimization Studio V12.3, Inc. Using the CPLEXR Callable Library and CPLEX Barrier and Mixed Integer Solver Options. 2011. http://www-01.ibm.com/software/integration/optimization/cplex-optimization-studio