1,721,028 research outputs found
Relaxations and solution methods for a class of nonlinear multicommodity network design formulations
No full text
From managing urban freight to smart city logistics networks
No full textWe present City Logistics by taking a systemic view, describing its main components and elements, as an emerging field of study with wide and significant social and economic impact. We then review contributions and identify some of the challenges that City Logistics raises, particularly for Operations Research and Transportation Science. The focus is on the network design issues relative to the system structure and services
Lagrangean-based decomposition algorithms for multicommodity network design problems with penalized constraints
No full textLagrangean decomposition for the fixed charge multicommodity network design problem
No full textTraditional Lagrangean relaxations for the multicommodity capacitated network design problem (MCNDP) involve dualizing either arc capacity or flow conservation constraints. The former (shortest-path relaxation) results in loosing the capacity structure whereas the latter (knapsack relaxation) does not maintain any information related to the network structure. Furthermore, both relaxations yield bounds that are at best equal to the value of the LP relaxation. This paper describes a new relaxation for the MCNDP, based on Lagrangean decomposition, which allows one to decompose the problem by nodes, and the subproblems partially preserve both the network and the capacity structure. This is, to the best of the authors' knowledge, the first relaxation for the MCNDP that theoretically yields better bounds than the LP relaxation
Decomposition algorithms for a class of nonlinear multicommodity network design problems
No full textThis paper discusses problems in the context of multicommodity network design where the additional constraints (such as capacity), rather than being imposed in a strict manner, are allowed to be violated at the expense of additional penalty costs. Such penalized cost structures allow these constraints to be treated as utilization targets and provide a better modelling framework in terms of strategic or tactical level planning of network design, especially in freight transportation systems. However, due to penalized costs, these problems are generally in the form of a nonlinear integer multicommodity network problem. This paper presents two algorithms based on Lagrangean relaxation and decomposition for the solution of such problems. The first is through relaxing flow constraints that results in an arc decomposition, and the second relies upon dualizing the capacity constraints that result in a flow decomposition. It is shown that nonlinearities in the decomposed substructures can be handled in a very efficient manner. Arc decomposition is shown, through computational experiments, to have better convergence properties. Through the proposed algorithms, reasonably good solutions can be obtained for these problems where publicly available state-of-the-art nonlinear optimization codes fail to identify feasible solutions
Minimizing greenhouse gas emissions in intermodal freight transport: An application to rail service design
No full textFreight transport has undesirable effects on the environment. The most prominent of these is greenhouse gas emissions. Intermodal freight transport, where freight is shipped from origin to destination by a sequence of at least two transportation modes, offers the possibility of shifting freight (either partially or in full) from one mode to another in the hope of reducing the greenhouse emissions by appropriately scheduling the services and routing the freight. Traditional planning methods for scheduling services in an intermodal transportation network usually focus on minimizing travel or time-related costs of transport. This article breaks away from such an approach by addressing the issue of incorporating environment-related costs (greenhouse gases, to be specific) into freight transportation planning and proposes an integer program in the form of a linear cost, multicommodity, capacitated network design formulation that minimizes the amount of greenhouse gas emissions of transportation activities. Computational results based on an application of the proposed approach on a real-life rail freight transportation network are presente
Lagrangean-based decomposition algorithms for multicommodity network design problems with penalized constraints
No full textThis paper discusses problems in the context of multicommodity network design where the additional constraints (such as capacity), rather than being imposed in a strict manner, are allowed to be violated at the expense of additional penalty costs. Such penalized cost structures allow these constraints to be treated as utilization targets and provide a better modelling framework in terms of strategic or tactical level planning of network design, especially in freight transportation systems. However, due to penalized costs, these problems are generally in the form of a nonlinear integer multicommodity network problem. This paper presents two algorithms based on Lagrangean relaxation and decomposition for the solution of such problems. The first is through relaxing flow constraints that results in an arc decomposition, and the second relies upon dualizing the capacity constraints that result in a flow decomposition. It is shown that nonlinearities in the decomposed substructures can be handled in a very efficient manner. Arc decomposition is shown, through computational experiments, to have better convergence properties. Through the proposed algorithms, reasonably good solutions can be obtained for these problems where publicly available state-of-the-art nonlinear optimization codes fail to identify feasible solutions
A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem
Full text linkThis paper presents an evolutionary algorithm for the fixed-charge multi- commodity network design problem (MCNDP), which concerns routing multiple commodities from origins to destinations by designing a network through selecting arcs, with an objective of minimizing the fixed costs of the selected arcs plus the variable costs of the flows on each arc. The proposed algorithm evolves a pool of solutions using principles of scatter search, interlinked with an iterated local search as an improvement method. New cycle-based neighbourhood operators are presented which enable complete or partial re-routing of multiple commodities. An efficient perturbation strategy, inspired by ejection chains, is introduced to perform local compound cycle-based moves to explore different parts of the solution space. The algorithm also allows infeasible solutions violating arc capacities while forming the “ejection cycles”, and subsequently restores feasibility by systematically applying correction moves
- …
