Search

International audience; The objective of the paper is to study the integration of revenue management considerations into service network design models targeting the tactical planning of intermodal consolidation-based freight transportation carriers. Revenue management strategies and mechanisms are broadly used within passenger transportation. Although identified as a desirable feature for freight transportation, interest growing within the industry, few contributions have addressed the topic. Moreover, almost none of those target the challenging issue of the interactions between the planning of the carrier’s services and operations, on the one hand, and the revenue-management strategy it could implement, on the other hand. We propose a new scheduled service network design model with resource and revenue management model, which selects the services and schedule to be repeatedly operated over the next season, allocates and routes the main resources supporting the selected services, and routes the demand flows between their respective origins and destinations. The objective of the model is the maximization of the expected net revenue of the carrier when several customer categories, with specific service requirements, as well as several tariff and operation classes are considered. Our interest goes beyond the modeling challenges raised by the problem setting, to exploring the impacts of this new approach on the decision types and on the structure of the service network solutions obtained. The results of extensive experiments, in terms of demand distribution, network topology, fare class and quality-of-service, provide a proof of concept of the proposed modeling framework and its capability for insightful analyses. Experimentation was conducted using an off-the-shelf software to solve the corresponding mixed-integer linear programming formulation for realistically dimensioned barge intermodal transportation instances.

We address the tactical-planning problem for an extended two-tiered City Logistics system. This more realistic problem setting, compared to the literature, integrates inbound and outbound demands, different transportation modes combining traditional, road-based, carriers with modes and vehicles of mass transport, such as light and regular rail. Aside from the assignment of customers to consolidation distribution centers and satellites, we manage a number of major resources, such as the multiple satellite capacity measures and the structure, allocation, and size of the heterogeneous fleets. We propose a scheduled service network design formulation for the tactical planning of such extended systems, and develop an efficient Benders decomposition algorithm, which includes a tailored partial decomposition technique for deterministic mixed-integer linear-programming formulations. The results of extensive numerical experiments show the efficiency of the proposed solution method, as well as the benefits of integrating several demand types and multimodal transportation networks into a single formulation.

This work focuses on a particular node of the intermodal chain of transportation, i.e. the maritime port area that represents the link between rail and sea transportation modes. Since this exchange node of the chain has not been addressed much yet, the aim of the present study is to provide a description of the process of rail operations in port area, to give an overview of the optimization challenges and to review the existing literature on it. The purpose of the paper is to attract the researchers attention on this particular intermodal node, where there is room for improvements.

We present a multi-ob’jective two-echelon vehicle routing problem with vehicle synchronization and ‘grey zone’ customers arising in the context of urban freight deliveries. Inner-city center deliveries are performed by small vehicles due to access restrictions, while deliveries outside this area are carried out by conventional vehicles for economic reasons. Goods are transferred from the first to the second echelon by synchronized meetings between vehicles of the respective echelons. We investigate the assignment of customers to vehicles, i.e., to the first or second echelon, within a so-called ‘grey zone’ on the border of the inner city and the area around it. While doing this, the economic objective as well as negative external effects of transport, such as emissions and disturbance (negative impact on citizens due to noise and congestion), are taken into account to include objectives of companies as well as of citizens and municipal authorities. Our metaheuristic – a large neighborhood search embedded in a heuristic rectangle/cuboid splitting – addresses this problem efficiently. We investigate the impact of the free assignment of part of the customers (‘grey zone’) to echelons and of three different city layouts on the solution. Computational results show that the impact of a ‘grey zone’ and thus the assignment of these customers to echelons depend significantly on the layout of a city. Potentially pareto-optimal solutions for two and three objectives are illustrated to efficiently support decision makers in sustainable city logistics planning processes.

We address the stochastic scheduled service network design problem with quality targets and uncertainty on travel times. This important problem, raising in the tactical planning process of consolidation-based freight carriers, has been little studied up to now. We define the problem considering quality targets for on-time operation of services and delivery of demand loads to destinations. We introduce a two-stage mixed-integer stochastic model defined over a space-time network, with quality targets modeled through penalties. We also propose an effective progressive-hedging-based meta-heuristic, based on a partial-decomposition concept aiming to address the challenges raised by the presence of flow-distribution decisions in the first-stage problem and by the flow-related degeneracy particular to network design. The results of an extensive numerical experimentation emphasize the worthiness of the formulation, as well as the very good performance of the proposed meta-heuristic when compared to a well-known commercial solver.

We propose a solution approach for stochastic network design problems with uncertain demands. We investigate how to efficiently use reduced cost information as a means of guiding variable fixing to define a restriction that reduces the complexity of solving the stochastic model without sacrificing the quality of the solution obtained. We then propose a matheuristic approach that iteratively defines and explores restricted regions of the global solution space that have a high potential of containing good solutions. Extensive computational experiments show the effectiveness of the proposed approach in obtaining high-quality solutions, while reducing the computational effort to obtain them.

Station-based bike-sharing systems rely on bike redistribution to provide users with an adequate service level. We propose a novel formulation of service network design that coordinates redistribution decisions in space and time to plan regular master tours. This formulation explicitly integrates resource-management decisions by considering a limited redistribution budget to acquire and operate vehicles, as well as an accurate time representation of pickups and deliveries of bikes at stations. We propose a matheuristic relying on a neighborhood search scheme to find solutions of good quality for real-world-sized problem instances in reasonable time. To produce starting solutions, we propose a construction heuristic decomposing the daytime redistribution process into three sequential phases: determine pickups and deliveries, link pickups and deliveries into transport requests, and assign transport requests to master tours. We evaluate the operational performance of master tours with a discrete-event simulation approach. We show that master tours improve the level of service in bike-sharing systems with high and regular mobility patterns, for example, commuting activities.

The shipment of hazardous materials is important and many of these products are flammable, explosive or radioactive. Despite high security standards, accidents still happen and the transportation of hazmat causes fear among the population. Therefore, the society expects authorities to distribute the risk fairly. To support such a fair distribution, we propose a new population-based risk definition that evaluates the risk for the population in any given area with respect to its multimodal transportation network. Moreover, we propose different objective functions for equilibrating the risk and extend the bilevel Hazmat Transport Network Design Problem by considering several transportation modes. In this problem, the government wants to equilibrate the risk among the population centers by restricting links to the shipment of hazardous goods. When taking that decision, the government has to anticipate the reaction of the carriers who want to minimize the transportation costs. This bilevel problem is transformed into a single-level mixed-integer linear program. The numerical results give insights to authorities (1) on how to evaluate risk for a fair distribution, and (2) that there is a positive convex relation between risk minimization and risk equilibration. The zones with high risk will initially benefit from the risk redistribution. However, pure equality just penalizes zones with low risk. Therefore, a significant improvement in risk distribution can be achieved at the cost of just a small increase in total risk. Moreover, compared to classical approaches in the literature, we achieve a better risk distribution among the population without increasing the total risk.

Many methods that have been proposed to solve large-scale MILP problems rely on the use of decomposition strategies. These methods exploit either the primal or dual structures of the problems by applying the Benders decomposition or Lagrangian dual decomposition strategy, respectively. In “The Benders Dual Decomposition Method,” Rahmaniani, Ahmed, Crainic, Gendreau, and Rei propose a new and high-performance approach that combines the complementary advantages of both strategies. The authors show that this method (i) generates stronger feasibility and optimality cuts compared with the classical Benders method, (ii) can converge to the optimal integer solution at the root node of the Benders master problem, and (iii) is capable of generating high-quality incumbent solutions at the early iterations of the algorithm. The developed algorithm obtains encouraging computational results when used to solve various benchmark MILP problems.

Classical Lagrangian relaxations for the multicommodity capacitated fixed-charge network design problem are the so-called flow and knapsack relaxations, where the resulting Lagrangian subproblems decompose by commodities and by arcs, respectively. We introduce node-based Lagrangian relaxations, where the resulting Lagrangian subproblem decomposes by nodes. We show that the Lagrangian dual bounds of these relaxations improve upon the linear programming relaxation bound, known to be equal to the Lagrangian dual bounds for the flow and knapsack relaxations. We also develop a Lagrangian matheuristic to compute upper bounds. The computational results on a set of benchmark instances show that the Lagrangian matheuristic is competitive with the state-of-the-art heuristics from the literature.

We propose a scheduled service network design model that simultaneously addresses strategic decisions regarding fleet sizing and allocation, including acquisition and outsourcing, as well as tactical decisions regarding a repeatable transportation plan and schedule. Moreover, as a well-sized fleet and a well-designed transportation plan should be able to accommodate fluctuations in freight volumes, the model takes the form of a stochastic program, explicitly addressing uncertainty in demand through the use of scenarios. This is the first model to consider this full suite of decisions while also recognizing uncertainty in freight volumes. Given the computational difficulties associated with solving stochastic programs exactly, we propose a column-generation-based matheuristics scheme for addressing the model, which decomposes the optimization problem across multiple dimensions, and evaluates a neighboring solution across all scenarios. This is the first heuristic scheme for this class of problem and we assess its effectiveness on two sets of instances. The first is a set generated to mimic the operations of a Less-than-truckload freight transportation carrier and the second is based on the network of a European postal carrier. We see that the solution approach is able to produce high-quality solutions for both sets of instances in run-times that are acceptable in practice.

Motivated by an actual problem of a national postal service company, we introduce and define a new two-echelon location-routing problem (2E-LRP). The 2E-LRP is defined in a two-echelon distribution...

This paper studies the two-echelon capacitated vehicle routing problem with time windows. The first echelon consists of transferring freight from depots to intermediate facilities (i.e., satellites), whereas the second echelon consists of transferring freight from these facilities to the final customers, within their time windows. We propose two path-based mathematical formulations for our problem: (1) in one formulation, paths are defined over both first- and second-echelon tours, and (2) in the other one, the first- and second-echelon paths are decomposed. Branch-and-price–based algorithms are developed for both formulations. We compare both formulations and solution methods on a comprehensive set of instances and are able to solve instances up to five satellites and 100 customers to optimality. This paper is the first paper in the literature that solves such large instance sizes. The online appendix is available at https://doi.org/10.1287/trsc.2018.0844 .

This paper studies the multi-commodity two-echelon capacitated vehicle routing problem with time windows. Specifically, we take customer-specific origin to destination, non-substitutable demands into account. The main components are: (i) first echelon tours, (ii) second echelon tours and (iii) movement of commodities from first echelon to second echelon, considering route connection and synchronization. Exploiting the structure of the problem, we propose a decomposition scheme which decouples the first and second echelon routing problems, by deleting the third component, and re-couples them by using constraints ensuring movement of commodities between the two echelons. Based on this decomposition, we present (i) a number of model formulations for the MC-2E-VRPTW, and (ii) develop an exact solution approach for this real-life problem. A computational study on a comprehensive set of instances shows the effectiveness in terms of computational effort and solution quality.

When demand for transportation is low or sparse, traditional transit cannot provide efficient and good-quality service, because of its fixed structure. For this reason, mass transit is evolving toward some degree of flexibility. Although the extension of Dial-a-Ride systems to general public meets such need of adaptability, it presents several drawbacks mostly related to the their extreme flexibility. Consequently, new transportation alternatives, such as demand-adaptive systems (DASs), combining characteristics from both the traditional transit and Dial-a-Ride, have been introduced. For their twofold nature, DASs require careful planning. We focus on tactical aspects of the planning process by formalizing the single-line DAS design problem with stationary demand and proposing two alternative hierarchical decomposition approaches for its solution. The main motivation behind this work is to provide a general methodology suitable to be used as a tool to build the tactical DAS plan in real-life conditions. We provide an experimental study where the two proposed decomposition methods are compared and the general behavior of the systems is analyzed when altering some design parameters. Furthermore, we test the versatility of our methods on a variety of situation that may be encountered in real-life conditions.

Benders decomposition is a broadly used exact solution method for stochastic programs, which has been increasingly applied to solve transportation and logistics planning problems under uncertainty. However, this strategy comes with important drawbacks, such as a weak master problem following the relaxation step that confines the dual cuts to the scenario subproblems. In this paper, we propose a partial Benders decomposition methodology, based on the idea of including explicit information from the scenario subproblems in the master. To investigate the benefits of this methodology, we apply it to solve a general class of two-stage stochastic multicommodity network design models. Specifically, we solve the challenging variant of the model where both the demands and the arc capacities are stochastic. Through an extensive experimental campaign, we clearly show that the proposed methodology yields significant benefits in computational efficiency, solution quality, and stability of the solution process.

To improve efficiency and sustainability in synchromodal logistics, it becomes crucial to mitigate the disruptive effects caused by non-synchronized operations. In this work, we study the Synchronized Location-Transshipment Problem in which the decisions on the facilities to select are fundamental to ensure the synchronization of flows and the correct exploiting of just-in-time logistics and cross-docking operations. We propose a Mixed-Integer Linear Programming formulation for the problem and perform an economic analysis to address several realistic situations based on different sizes of the transshipment facilities and location types. The results of the tests allow us to derive managerial insights and to define future research lines.

Service Network Design designates issues, decisions, and network-design models aimed to plan the activities and resources of the supply side of a transportation system, aiming to satisfy demand efficiently, profitably, and within the quality standards agreed upon with the customers generating this demand. Service Network Design is particularly relevant in the context of consolidation-based transportation, an umbrella term for companies and systems which group and transport within the same vehicle several freight loads of different customers, aiming for a profitable balance between economy-of-scale-based costs and high service quality for customers. This chapter presents a comprehensive overview of the general Service Network Design methodology, in terms of models, solution methods and utilization, that cuts across application fields, including railroads, less-than-truckload motor carriers, land and water-based intermodal transport, regular and express postal services, and city logistics.

Network design problems arise whenever optimal choices have to be made that can be represented conceptually as the selection of a subset of links in a graph. Typically, these optimal choices are the result of complex tradeoffs between various types of costs and constraints. In particular, most network design problems involve fixed costs associated with link selection and variable costs associated with flows (of people, goods, information,…). Because of their combinatorial nature and the complexity of their objective functions and constraints, network design problems are inherently difficult (most of them are \(\mathcal {N}\mathcal {P}\)-hard). For this reason, models and algorithms for network design problems involve approaches from several areas of combinatorial optimization and mathematical programming.

This chapter introduces problems and models that involve design decisions captured with arc-based binary variables that typically model fixed costs. We distinguish whether the demand can be represented as a single commodity or as multiple commodities, whether or not there are capacities, and whether or not there are variable transportation costs in the objective function, in addition to the fixed design costs. These characteristics yield different variants of network design problems and models, with various degrees of complexity. We identify a few basic modeling approaches in network design, including the use of path flow variables instead of arc flow variables, and the derivation of cut-set-based inequalities.

Rail transportation provides economically-priced, environmentally-friendly, and timely freight transportation services at the regional, national, and international levels. To achieve this performance, railroads operate mostly according to a double consolidation policy, as cars are grouped into blocks, which are grouped into trains, and set up tactical operations plans specifying the train services and schedules to operate, the blocks to build at each terminal, the routing of blocks and cars, and the resource assignment to support these operations. Tactical planning makes up a very complex problem, with many facets and decisions linked in a web of economic, resource utilization, and time-performance objectives, limitations, and trade-offs. Operations Research provides the Service Network Design methodology to build the railroad tactical plan making the most efficient use of the railroad’s resources to achieve its economic and customer-service performance objectives. The chapter reflects this important relation between railroad planning and network design. It focuses on service network design models for railroad tactical planning, targeting both particular activities, such as car blocking and train makeup, and integrated network-wide planning processes.

Heuristics and metaheuristics are widely used to tackle difficult network design problems. We first present fundamental concepts for the development of heuristic approaches, such as search spaces, neighborhoods, and populations of solutions. The main heuristic and metaheuristic solution methods are then introduced: constructive and Local Search heuristics, neighborhood-based metaheuristics, population-based methods, matheuristics, parallel meta- and matheuristics. The chapter focuses on the application of these methods to fixed-charge transportation and multicommodity capacitated fixed-charge network design problems. We also provide a historical perspective on the development of the field since the 1960’s, as well as a number of challenging research avenues for meta- and matheuristics for network design problems.

This chapter is dedicated to exact algorithms for single-commodity and multicommodity fixed-charge network design. These problems are notoriously difficult, since they are in general strongly \(\mathcal {N}\mathcal {P}\)-hard. In addition, their objective function includes both fixed design costs and variable transportation costs, which results in complex tradeoffs that complicate the task of finding optimal solutions. Multicommodity capacitated fixed-charge problems are particularly challenging, since even their LP relaxations are difficult to solve, as they are often highly degenerate. In addition, the formulations of these problems display a large number of both variables and constraints. In this context, decomposition methods that exploit subproblem structures are useful to seek optimal solutions for such problems. This chapter is divided into three parts. Part I presents relaxations that can improve the quality of the lower bounds, while exploiting the subproblem structures. Part II focuses on enumeration algorithms that use the modeling techniques covered in Part I. Part III is dedicated to the solution of large-scale instances by combining the advanced enumeration algorithms of Part II with heuristic methods and by exploiting parallel computing.

This paper proposes a solution approach for the multicommodity capacitated fixed-charge network design problem with uncertain demand modeled as a two-stage stochastic program. The proposed learning-based matheuristic combines heuristic search techniques with mathematical programming. It provides a systematic approach to identifying structures of good-quality solutions by gradually considering scenarios and their influences on design decisions. Extensive computational experiments illustrate the efficiency of the proposed matheuristic in obtaining high-quality solutions with limited computational efforts.