Railway capacity management in the Swedish national freight transport model, Samgods, using linear programming

Abstract

Railway Capacity Management in the Swedish National Freight Transport Model, Samgods, using Linear Programming Conference: 2ND Symposium of the European Association for Research in Transportation, Stockholm, Sweden, September 2013. Author: Dr. Henrik Edwar ds Vectura Consulting Svetsar vägen 24 171 11 SOLNA, SWEDEN Henrik.Edwar ds@vectura.se

Abstract Studies made of the national freight model in Sweden around the year 2000 came to the conclusion that it had to be updated to better serve as an instrument for policy analysis and cost-benefit analysis of infrastructure investments at the national level. One basic idea was to acquire data on commodity flows from producers to consumers, and to construct models for goods transport demand and logistics solutions. A summary of the analysis is presented in SIKA [2004] 1. This led to a number of ambitious commodity flow surveys (2001 and 2004/05) that together with foreign trade statistics, business registers and socioeconomic data provided the base for construction of so called base matrices for the year 2005.

SIKA (2004): The Swedish National Freight Model: A critical review and an outline of the way ahead, Samplan 2004:1, SIKA, Stockholm.

The development of a logistics model was commissioned to a consortium led by Rand Europe, among which the key persons involved since then has moved to a smaller consulting firm. The implemented model is described in de Jong et al [2011] 2. A key concept introduced is the ADA-principle, which stands for Aggregate-DisaggregateAggregate principle, meaning that the model operates at aggregate levels on the demand side, and on the final assigned vehicles flows in the transport network. The disaggregate step involves: 1. Splitting up the zone-zone demand into combinations of firm-to-firm demands, where each pairwise combination of small, medium-sized and large firms comprises a number of firm to firm relations. 2. Simulation of logistics behavior in the firm to firm relations, comprising inventory holding considerations and selection of transport chains providing the minimum total costs. Decisions for each firm to firm relation concern the choice of shipment size, transport chain with transfer locations between modes (using a set of optional, predefined transport chain types) and vehicle size for each leg in the transport chain. In its present form capacity constraints with respect to flow on different links are not considered. This is required to enable feasible solutions with respect railway flows in particular. In order to handle this we are evaluating whether a linear programming model, with column generation, for railway capacity modeling can be made operational together with the basic logistics model. The capacity is measured in terms of summarized number of loaded and empty freight trains on bidir ectional railway links. Efficient computation of the train loads on the links are enabled by using the spanning trees determining the railway paths with the least generalized costs, especially since only a single path is used per railway origin-destination-relation. Initially a default factor per railway type is used for determining the load of empty trains. To ensure that a feasible solution can be identified we initially add a second column, not using railway if possible, selected from a few alternative transport chain solution alternatives. In practice this will allow us to identify a feasible solution, but just in case we also introduce the possibility to acquire additional, fictitious, capacity inside the LP-model. The idea is to use the dual values (= marginal costs) from these capacity constraints and feed them back into the cost function of the logistics model. With this functionality in place we will iterate a reasonable number of times (between the logistics model and the LP model) and generate additional columns to the LP-model were appropriate, managing only transport chains initially using railway, to find a good enough solution using the introduced marginal costs.

de Jong Gerard, Ben-Akiva Moshe and Baak Jaap (2011): Method Report - Logistics Model in the Swedish National Freight Model System (Version 2), Significance, Deliverable 6b for the Samgods group D6b, Project 10060, January.

When finalized the set of transport chains with and without railway use will be assembled into a final solution that satisfies the capacity constraints. Should the marginal costs not ensure that a feasible solution is identified we may resort to use the linear programming solutions directly, i e to use the transport chains (= columns) selected by the optimizer. This may call for the use of a rounding off procedure of some kind. Possibly the actual solution in a producer consumer relation could be split into using two or more transport chains, but this is not yet an option in the logistics model. A more advanced alternative then could be to formulate a smaller mixed integer linear programming problem for the split alternatives concerned, and by this enforce the use of integer solutions. The purpose of this paper is simply to present how well this column generation LP method performs on regular size problems for the national freight model Samgods. The project is financed by the national Transport Administration in Sweden.

Keywor ds: logistics, capacity management, railway transports, column generation, linear programming