Exact and Heuristic Optimization Algorithms for Auto-Rack Loading Problem


  • Ashok Vishwanathan
  • Bharath Narayanan
  • Nagen Nagarur Binghamton University




Vehicle Transportation, Heuristics, Finished Vehicle Delivery, Rail, Knapsack Problem


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.


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.



How to Cite

Vishwanathan, A., Narayanan, B., & Nagarur, N. (2022). Exact and Heuristic Optimization Algorithms for Auto-Rack Loading Problem. Industrial and Systems Engineering Review, 10(1), 55-73. https://doi.org/10.37266/ISER.2022v10i1.pp55-73