Featured Story January-February 2014
Multi Commodity Network Design

by Dr. Dimitris Paraskevopoulos, School of Management, University of Bath

Tactical planning of freight/passenger transportation systemsinvolves complex problems that aim at minimizing the total operational costs and maximizing the service level delivered to the customers/passengers. Designing routes, developing the timetable and determining the appropriate service frequency are focal problems that arise in tactical planning of a transportation system. Given the timetable, one has to further allocate the right vehicles with the appropriate capacity to the economically efficient routes, such that the capacity utilization is maximized. Moreover, crew schedules must be developed coherent with legal, social and technical requirements. Railways, airlines and less-than-truckload motor carriers are typical examples of such systems.

The above tactical planning problems are difficult to solve due to their default high complexity and the interrelations amongst them as well as due to the variety of constraints and objectives (contradictory or not) they impose. Operations research methods and computationally efficient algorithms have been developed to tackle these problems and assist the dispatchers in the decision making processes. Towards this end, the model of the Multi-Commodity Network Design Problem (MCNDP) has been widely used to describe tactical planning transportation problems.

The MCNDP can be defined on a graph of nodes and links(Ahuja et al., 1993). The links are typically directed and represent the arcs of the network. The nodes represent either the origins or destinations or both, of a particular transportation demand of a single or multiple commodities (e.g. freight, passengers). Each link has a fixed cost, length and capacity. The fixed cost is considered when a particular link is used, while there are variable costs, coupled with each used link, related to the commodity flow. The capacity depicts the volume of the traffic that a link can hold. The objective is to select a subset of links of the network to satisfy all the transportation requests of the nodes and to determine how much and which commodity will travel via each link such that the total fixed and variable costs are minimized.

Figure 1a illustrates a typical network/ graph of nodes and links (they could be arcs on a directed graph). Different colours depict different commodities that need to travel from an origin to a destination. The goal is to select a sub-graph to satisfy this need, as Fig. 1b shows, without violating any capacity constraints at links and while minimising the total fixed cost of establishing the links and variable cost of traversing the commodities. Note that the commodities may be split and follow parallel paths and meet at an intermediate node or at the destination. For the sake of simplicity this is not illustrated in Fig 1b.
Copyright 2013 Website Design by Pantelis Lappas. All rights reserved.
M A N A G E M E N T    S C I E N C E    L A B O R A T O R Y   

ACADEMICS
........................

RESEARCH
........................

PEOPLE
........................

MS SUPPORT
........................

ARCHIVE
......................

DOWNLOAD
......................

ABOUT
..................

CONTACT
..................
Fig. 1a Typical Network of Nodes and Links
Fig. 1b Typical MCNDP solution.
The MCNDP has attracted much attention in the literature due to both its complexity, which is NP-hard in the strong sense, and the wide variety of applications in the areas of telecommunications, logistics, production and transportation systems (Balakrishnanet al., 1997).  Despite the significant efforts devoted to the development of exact methodologies for the MCNDP (Hewittet al, 2012), the literature still favours heuristic approaches when large scale problem instances are concerned.  One of the most successful local search strategies for the MCNDP was proposed in (Ghamloucheet al. 2003), who introduce new cycle-based neighbourhood operators in a tabu search framework. The cycle based operators were later on used within a path-relinking algorithm (Ghamloucheet al. 2004), a multilevel cooperative framework (Crainicet al. 2006), and scatter search (SS) (Crainic and Gendreau, 2007). With regard to the latter paper, the authors concluded that the proposed SS did not meet their expectations and further experimentation should be done to realise the full benefits of the SS.

Crainicet al. (2000) propose a simplex-based tabu search method for the MCNDP on a path-flow based formulation of the problem. Their method combines column generation with pivot-like moves of single commodity flows to define the path flow variables. In a similar fashion, Ghamloucheet al. (2003) describe cycle-based neighbourhoods for metaheuristics aimed at MCNDPs. The main idea of the cycle-based local moves is to redirect commodity flows around cycles in order to change close existing arcs to open new ones. This concept has helped to enrich the solution neighbourhood, since multiple commodities can now be considered for relocation and the range of moves is broader because flow redirections are no longer restricted to paths linking origins and destinations. The same authors use the proposed neighbourhood structures in a tabu search algorithm, where a commodity flow sub-problem is solved to optimality at each local search iteration.

Ghamlouche at al. (2004) proposed an evolutionary algorithm for the MCNDP. The authors developed solution framework based on path relinking, in which cycle-based neighbourhoods are used for generating the elite candidate set of solutions via a tabu search algorithm and for moving from the initial to the guiding solution.  Various rules were presented for choosing the initial and guiding solutions. The dissimilarity of solutions was considered as an additional to the solution cost criterion for updating the pool of solutions.  Following the evolutionary algorithm, Alvarez et al. (2005) proposed a SS algorithm for the MCNDP. The authors used GRASP, originally proposed by Feo and Resende (1995), to produce a diversified initial set of solutions.  Each commodity path is put through a post improvement process. The solutions are combined by choosing the best path for each commodity, among the solutions that are being combined.  A feasibility restoration mechanism is incorporated if needed.  The authors randomly generated their own benchmark instances to evaluate the performance of the proposed methodology. Crainicet al. (2006) proposed a multilevel cooperative search on the basis of local interactions among cooperative searches and controlled information gathering. The authors focused on the specification of the problem instance solved at each level and the definition of the cooperation operators.

More recently, Katayama et al. (2009) proposed a column and row generation heuristic for solving the MCNDP. The main idea stems from the relaxation of the arc capacity constraint, while a column and row generation technique is developed to solve the relaxed problem. Hewitt et al. (2010) describe a solution approach for the MCNDP based on a combination of mathematical programming algorithms and heuristic search techniques. The proposed methodology uses very large neighbourhood search in combination with an IP solver on an arc-based formulation of the MCNDP, and a linear programming relaxation of the path-based formulation using cuts discovered during the neighbourhood search. Hewitt et al. (2012) extend this work by introducing a generic branch and price guided algorithm for integer programs with application to the MCNDP.

Research, on solving MCNDPs, is heading towards collaborative frameworks that combine heuristic and exact methodologies, to enable high quality solutions in reasonable computational times. Given that the MCNDP refers to tactical planning problems, finding solutions in seconds does not make significant difference on the final outcome, and therefore the focus is more on obtaining higher quality solutions to large scale MCNDPs. As the MCNDP is a focal problem with a wide variety of applications, rich variants with multi-criteria and peculiar objectives and constraints (e.g., risk and robustness measures, congestion charges at nodes and links) is a promising yet unexplored research avenue.

Bibliography

Ahuja, R., T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall:Englewood Cliffs, NJ, 1993.

Alvarez, A.M., J.L. Gonzalez-Velarde and K. De-Alba, "Scatter search for network design problem'', Annals of Operations Research, 138, 159--178, 2005.

Balakrishnan, A., Magnanti, T. L., and Mirchandani, P. (1997). "Network Design''. Dell' Amico, Mauro, Maffioli, Francesco, and Martello, Silvano (eds.): Annotated Bibliographies in Combinatorial Optimization. Wiley, New York, USA, 311--334.

Crainic T.G., Gendreau M. (2007). "A Scatter Search Heuristic for the Fixed-Charged Capacitated Network Design Problem'', Metaheuristics - Progress in Complex Systems Optimization, Vol. 39, Operations Research/Computer Science Interfaces Series, K.F. Doerner, M. Gendreau, P. Greistorfer, W.J. Gutjahr, R.F. Hartl, and M. Reimann (Eds.), Springer, New York, NY, 25--40.

Crainic, T., M. Gendreau and J. Farvolden, "A simplex-based tabu search for capacitated network design'', INFORMS Journal on Computing, 12, 223--236, 2000.

Crainic, T.G., Y. Li and M. Toulouse, "A first multilevel cooperative algorithm for capacitated multicommodity network design'', Computers and Operations Research, 33, 2602--2622, 2006.

Crainic, TG, Frangioni, A, and Gendron, B (2001). "Bundle-Based Relaxation Methods for Multicommodity Capacitated Network Design''. 112,  Discrete Applied Mathematics 112, 73--99.

Feo, T.A. and M.G.C. Resende. "Greedy Randomized Adaptive Search Procedures.'' Journal ofGlobal Optimization 6(2), 109--133, 1995.

Ghamlouche, I.,  T.G. Crainic and M. Gendreau, "Cycle-based Neighborhoods for fixed-charge capacitated multicommodity network design'', Operations Research, 51, 655--667, 2003.

Ghamlouche, I., T.G. Crainic and M. Gendreau, "Path relinking, cycle-based neighborhoods and capacitated multicommodity network design'', Annals of Operations Research, 131, 109--134, 2004.

Hewitt M, Nemhauser GL, Savelsbergh MWP (2010) Combining exact and heuristic approaches for the capacitated fixed-chargenetwork flow problem. INFORMS Journal on Computing 22(2), 314--325.

Hewitt, M., Nemhauser, G., Savelsbergh, M.W. (2012). Branch and price guided search for integer programs with an application to the multicommodity fixed-charge network flow problem. INFORMS Journal on Computing, http://dx.doi.org/10.1287/ijoc.1120.0503, 1--15.

Katayama, N., M. Chen and M. Kubo, "A capacity scaling heuristic for the multicommodity capacitated network design problem'', Journal of Computational and Applied Mathematics, 232, 90--101, 2009.