The Special Application of Vehicle Routing Problem with Uncertainty Travel Times: Locomotive Routing Problem

Document Type : Research Paper

Authors

1 Assistant Professor, Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

2 Deputy Director General ,Information and Communication Technology Office, Iran Railways Company, Tehran, Iran

Abstract

This paper aims to study the locomotive routing problem (LRP) which is one of the most important problems in railroad scheduling in view of involving expensive assets and high cost of operating locomotives. This problem is assigning a fleet of locomotives to a network of trains to provide sufficient power to pull them from their origins to destinations by satisfying a rich set of operational constraints and minimizing the total operational cost. This problem is the special application of vehicle scheduling and it is modeled by using the vehicle routing problem with time windows (VRPTW) to optimal assignment of locomotives to assembled trains. Almost all of the prior models were deterministic and an important issue, widely ignored in prior research in locomotive optimization, is the presence of significant sources of uncertainty in transit times, travel times and changes to the train schedule. Therefore, in this paper unlike most of the work where all the times are deterministic, uncertainty in travel time is considered. Because travel times in reality fluctuate due to a variety of factors and its understanding and management in transportation networks is very important. The concepts of fuzzy sets and fuzzy control systems are considered to model the uncertainty in travel times. Besides, a genetic algorithm (GA) with various heuristics is proposed to tackle the proposed model and its performance is evaluated in different steps on various test problems generalized from a set of instances in the literature. The computational experiments on data sets illustrate the efficiency and effectiveness of the proposed approach. 

Keywords

References

-Ahuja, R. K., Liu, J., Orlin, J. B., Sharma, D. and Shughart, L.A. (2005) "Solving real-life locomotive scheduling problems", Transportation Science, Vol.39, No.4, pp. 503-517.
-Booler, J. M. P. (1980) "The solution of a railway locomotive scheduling problem", Journal of Operational Research Society, Vol. 31, No. 10, pp. 943-948.
-Bouzaiene-Ayari, B., Clark Cheng, Sourav Das, R. F. and Powell, W. B. (2014) "From single commodity to multi attribute models for locomotive optimization: a comparison of optimal integer programming and approximate dynamic programming", Transportation Science, Vol. 50, No. 2, pp.1-24.
-Chiang, T. C. and Hsu, W.H. (2014) "A knowledge-based evolutionary algorithm for the multi objective vehicle routing problem with time windows", Computers & operations Research, Vol. 45, No.1, pp.25-37.
-Cordeau, J. F., Desauliniers, G., Lingaya, N., Soumis, F. and Desrosiers, J. (2001) "Simultaneous locomotive and car assignment at VIA Rail Canada", Transportation Research Part B, Vol. 35, No. 8, pp. 767-787.
-Cordeau, J. F., Soumins, F. and Desrosiers, J. (2000)"A bender decomposition approach for the locomotive and car assignment problem", Transportation Science, Vol. 34, No.4, pp.133-149.
-Cordeau, J. F., Toth, P. and Vigo, D. (1998) "A survey of optimization models for train and scheduling", Transportation Science, Vol. 32, No.4, pp.988-1005. 
-Dhahri, A., Zidi, K. and Ghedira, K. (2014) "Variable neighborhood search based set covering ILP model for the vehicle routing problem with time windows", Procedia Computer Science, Vol.29, pp.844-854.
-Fischetti, M. and Toth, P. (1997) "A package for locomotive scheduling", Italy: University of Blogna.
-Florian, M., Bushell, G., Ferland, J., Guerin, G. and Nastansky, L. (1976) "The engine scheduling problem in a railway network", Information Systems and Operational Research, Vol.14, No.2, pp. 121-138.
-Forbes, M. A., Holt, J. N. and Walts, A.M. (1991) "Exact solution of locomotive scheduling problem", Journal of the Operation Research Society, Vol.42, No.10, pp. 825-831.
-Ghannadpour, S. F., Noori, S. and Tavakkoli-Moghaddam, R. (2014) "A multi-objective vehicle routing and scheduling problem with uncertainty in customers’ request and priority", Journal of Combinatorial Optimization, Vol.28, No.2, pp.414-446.
-Ghoseiri, K. and Ghannadpour, S. F. (2009) "Locomotive routing problem using a hybrid genetic algorithm", Journal of Transportation Research, Vol. 5, No.3, pp.259-273.
-Ghoseiri, K. and Ghannadpour, S. F. (2010) "A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows", Applied soft computing, Vol. 10, No.1, pp. 53-65.
-Hiermann, G., Puchinger, J., Ropke, S. and Hartl, R.F. (2016) "The electric fleet size and mix vehicle routing problem with time windows and recharging stations", European Journal of Operational Research, Vol. 252, No.3, pp.995-1018.
-Higgins, A. and Kozan, E. (1997) "Heuristic techniques for single line train scheduling ", journal of Heuristics, Vol. 3, No.43, pp. 43-62.
-Holland, J. H. (1975) "Adaptation in natural and artificial system", USA: University of Michigan Press.
-Hosseini Motlagh, S. M., Majidi, S., Yaghoubi, S. and Jokar, A. (2017) "Fuzzy green vehicle routing problem with simultaneous pickup-delivery and time windows", RAIRO-Operations Research, DOI: https://doi.org/10.1051/ro/2017007
-Kasalica, S., Mandić, D. and Vukadinović, V. (2013) "Locomotive assignment optimization including train delays", Traffic&Transportation, Vol. 25, No.5, pp. 421-429.
-Majidi, S., Hosseini Motlagh, S.M. and Ignatius, J. (2017) "Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery", Soft Computing, DOI: https:// doi:10.1007/s00500-017-2535-5.
-Miranda, D. M. and Conceição, S.V. (2016) "The vehicle routing problem with hard time windows and stochastic travel and service time", Expert Systems with Applications, Vol. 64, No.3, pp.104-116.
-Parandin, N. and Fariborzi Araghi, M. A. (2008) "Ranking of fuzzy numbers by distance method", Journal of Applied Mathematics, Vol. 5, No.19, pp.47-55. 
-Pashchenko, F. F., Kuznetsov, N. A., Ryabykh , N.G. Minashina, I.K., Zakharova , E.M. and Tsvetkova, O. A. (2015) "Implementation of train scheduling system in rail transport using assignment problem solution", Procedia Computer Science, Vol. 63, pp. 154-158.
-Pepin, A. S., Desaulniers, G., Herts, A. and Huisman, D. (2009) "A comparison of five heuristics for the multiple depot vehicle scheduling problem", Journal of Scheduling, Vol. 12, No.17, pp. 17-30.
-Piu, F. and Speranza, M. G. (2014) "The locomotive assignment problem: a survey on optimization models", International Transaction in Operational Research, Vol. 21, No. 3, pp. 327-352.
-Piu, F., Kumar, V. P., Bierlaire, M. and Speranza, M.G. (2015) "Introducing a preliminary consists selection in the locomotive assignment problem", Transportation Research Part E-Logistics And Transportation Review, Vol. 82, No.3, pp. 217-237.
-Powell, W. B., Bouzaiene‐Ayari, B., Lawrence, Clark Cheng and Sourav Das, R. F. (2012) "Strategic, tactical and real‐time planning of locomotives at Norfolk Southern using approximate dynamic programming", Philadelphia: American Society of Mechanical Engineers (ASME).
-Qamsari, A. S. N, Hosseini Motlagh, S. M. and Jokar, A. (2017) "A two-phase hybrid heuristic method for a multi-depot inventory-routing problem", International Journal of Transportation Engineering, Vol. 4, No. 4, pp. 287-304.
-Rouillon, S., Desaulniers, G. and Soumis, F. (2006) "An extended branch-and-bound method for locomotive assignment", Transportation Research Part B, Vol. 40, No. 5, pp. 404-423.
-Samani, M. Gh. and Hosseini Motlagh, S. M. (2017) “A Hybrid algorithm for a two-echelon location- routing problem with simultaneous pickup and delivery under fuzzy demand”, International Journal of Transportation Engineering, Vol. 5, No. 1, pp. 59-85.
-Solomon, M. M. (1987) "Algorithms for vehicle routing problem and scheduling problems with time window constraints", Operation Research, 35, 254-365.
-Teichmann, D., Dorda, M., Golc, K. and Bínová, H. (2015) "Locomotive assignment problem with heterogeneous vehicle fleet and hiring external locomotives", Mathematical Problems in Engineering, Vol. 2015, No. 2015, pp.1-7.
-Torres, L.M. (2003) "online vehicle routing: set partitioning problems", Berlin: Technischen Universität Berlin. 
-Vaidyanathan, B., Ahuja, R. K. and Orlin, J. B. (2008) "The locomotive routing problem", Transportation Science, Vol.42, No. 4, pp.492-507.
- Vaidyanathan, B., Ahuja, R. K., Liu, J. and Shughart, L. A. (2008) "Real-life locomotive planning: New formulations and computational results", Transportation Research Part B: Methodological, Vol.42, No. 2, pp.147-168.
-Yaghini, M. and Lessan, J. (2010) "Railway operation planning", Iran: Iran University of Science & Technology (IUST).
-Yaghini, M., Sharifian, S. and Akhavan, R. (2012) "Reengineering the locomotive operation management process in the railways of Iran (RAI)", Procedia - Social and Behavioral Sciences, Vol. 43, pp.86-97.
-Ziarati, K., Chizari, H. and Mohammadi Nezhads, A. (2005) "Locomotive optimization using artificial intelligence approach", Iranian Journal of Science & Technology, Vol. 29, No. B1, pp.93-105.
 
 
International Journal of Transportation Engineering
Volume 5, Issue 2 - Serial Number 18
October 2017
Pages 119-136

Files

Share

How to cite

Statistics