Exact and Heuristic Optimization Algorithms for Auto-Rack Loading Problem
DOI:
https://doi.org/10.37266/ISER.2022v10i1.pp55-73Keywords:
Vehicle Transportation, Heuristics, Finished Vehicle Delivery, Rail, Knapsack ProblemAbstract
The transportation of new vehicles over the rail network takes place in specially designed railcars / wagons called auto-racks. This paper introduces a new problem – Auto-Rack Loading Problem (ARLP), involving transportation of vehicles on auto-racks with the objective of maximizing the revenue from the loaded vehicles subject to constraints. Existing literature only addresses methods to model and optimize transportation of vehicles on trucks called the auto-carrier loading problem. Initially, a model is formulated as an integer programming problem which is proven to be NP-hard since a special case of the ARLP reduces to a 0-1 multiple knapsack problem. Consequently, a multi-phase heuristic procedure is developed to solve large instances of the problem in reasonable time. The performance of the integer programming model and the heuristic procedure are evaluated and compared with an upper bound for randomly generated instances involving auto-racks and vehicles designed for use in the Indian rail network.
References
Andonov, R., Poirriez, V., & Rajopadhye, S. (2000). Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research, 123(2), 394-407.
Association of American Railroads. (2009). Association of american railroads. Manual of standards and recommended practices Section N Multi-level manual. Transportation Technology Center, AAR, Cary, NC, I24-I25.
Association of American Railroads. (2016) The environmental benefits of moving freight by rail. Retrieved from https://www.aar.org/BackgroundPapers/Environmental Benefits of Moving Freight by Rail.pdf
Backaker L., & Krasemann. J. T. (2012). Trip plan generation using optimization: A benchmark of freight routing and schedulling policies within the carload service segment. Journal of Rail Transport Planning & Management, 2(1-2), 1-13.
Bonassa, A. C., Cunha, C. B., & Isler, C. A. (2019). An exact formulation for the multi-period auto-carrier loading and transportation problem in Brazil. Computers & Industrial Engineering, 129, 144-155.
Burke, E.K., Silva, J. D. L., & Soubeiga, E. (2005). Multi-objective hyper-heuristic approaches for space allocation and timetabling. In Metaheuristics: Progress as Real Problem Solvers (pp. 129-158). Springer, Boston, MA.
Chekuri, C., & Khanna, S. (2005). A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 35(3), 713-728.
Cordeau. J. F., Dell’Amico, M., Falavigna, S., & Iori, M. (2015). A rolling horizon algorithm for auto-carrier transportation. Transportation Research Part B, 76, 68-80.
Dolinayova. A., Loch, M., & Kanis, J. (2015). Modelling the influence for wagon technical parameters on variable costs in rail freight transport. Research in Transport Economics, 54, 33-40.
Eskigun, E., Uzsoy, R., Preckel, P. V., Beaujon, G., Krishnan, S., & Tew, J. (2005). Outbound supply chain network with mode selection, lead times and capacitated vehicle distribution centers. European Journal of Operational Research, 165(1), 182–206.
Feuerman, M., & Weiss, H. (1973). A mathematical programming model for test construction and scoring. Management Science, 19(8), 961-966.
Governnment of India. (2013). Final maximum permissible speed certificate for operation of Broad Gauge Bogie Covered Autocar carrier wagon type BCACBM. Retrieved from www.rdso.indianrailways.gov.in/works/uploads/File/Final Speed ceritificate of BCACBM Wagon(1).pdf
Islam, D. M. Z., Jackson, R., Robinson, M. (2015). European freight rolling stock fleet size in 2050 in light of Transport White Paper 2011. Journal of Rail Transport Planning & Management, 5, 195-210.
Joiner, S. (2010). Is bigger better? Monster Trains vs Freight Trains. Popular Mechanics. Online Edition.
Khuri, S., Bäck, T., & Heitkötter, J. (1994). The zero/one multiple knapsack problem and genetic algorithms. In Proceedings of the 1994 ACM symposium on Applied computing (pp.188-193).
Kumar, R., Joshi, A. H., Banka, K. K., & Rockett, P.I. (2008). Evolution of hyperheuristics for the biobjective 0/1 knapsack problem by multiobjective genetic programming. In Proceedings of the 10th annual conference on Genetic and evolutionary computation (pp.1227-1234).
Lin. C-H. (2010). An exact solving approach to the auto-carrier problem. Journal of Society for Transportation and Traffic Studies, 1, 93-107.
Martello, S., & Toth, P. (1984). A mixture of dynamic programming and branch-and-bound for the subset-sum problem. Management Science, 30(6), 765-771.
Martello, S., & Toth, P. (1990). Knapsack Problems. 1st Edition. West Sussex, England: John Wiley & Sons (pp.221–240).
Martello, S., Pisinger, D., & Toth, P. (1999). Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45(3), 414-424.
Pisinger, D. (1999). An exact algorithm for large multiple knapsack problems. European Journal of Operational Research, 114(3), 528-541.
Plateau, G., & Elkihel, M. (1985). A hybrid method for the 0-1 knapsack problem. Methods of Operations Research, 49, 277-293.
Poirriez, V., Yanev, N., & Andonov, R. (2009). A hybrid algorithm for the unbounded knapsack problem. Discrete Optimization, 6(1), 110-124.
Shah-Hosseini, H. (2008). Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem. International Journal of Intelligent Computing and Cybernetics, 1(2), 193-212.
Touax. (2016). 4-axle wagon for automotive transportation. Retrieved from http://www.touaxtexmaco.com/content/bcacbm-rake
Transport Canada. (2013). Overview of rail transportation. Retrieved from http://www.tc.gc.ca/eng/policy/anre-menu-3020.htm
Turner, K., & Williams, G. (2004). Modeling complexity in the automotive supply chain. Journal of Manufacturing Technology Management, 16(4), 447–458.
Viswanathan, A., Wang, S., Joshi, A., Jones, L., & Srihari, K. (2011). Estimation of claims in an outbound automotive supply chain using capture-recapture methodology. International Journal of Logistics Research and Applications, 14(1), 1-10.
Wang, Y., & Chen F. (2019). Auto-carrier Loading Problem with Inter-set Costs in Urban Outbound Logistics of Automobiles. In Proceedings of 2019 IEEE International Conference on Smart Manufacturing, Industrial & Logistics Engineering (SMILE) (pp.164-168).
Yee. J. (2014). A dynamic optimization for automotive vehicle shipment and delivery. Journal of the Korea Society for Simulation, 23(4), 9-19.
Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, In IEEE transactions on Evolutionary Computation, 3(4), 257-271.
Published
How to Cite
Issue
Section
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
The copyediting stage is intended to improve the flow, clarity, grammar, wording, and formatting of the article. It represents the last chance for the author to make any substantial changes to the text because the next stage is restricted to typos and formatting corrections. The file to be copyedited is in Word or .rtf format and therefore can easily be edited as a word processing document. The set of instructions displayed here proposes two approaches to copyediting. One is based on Microsoft Word's Track Changes feature and requires that the copy editor, editor, and author have access to this program. A second system, which is software independent, has been borrowed, with permission, from the Harvard Educational Review. The journal editor is in a position to modify these instructions, so suggestions can be made to improve the process for this journal.
