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.

We study the value of deterministic solutions, in particular their quality and upgradability, in addressing stochastic network design problems, by analyzing their time-dependent formulations known as scheduled service network design problems in freight transportation planning. We study several problem variants and models and investigate, for each case, the immediate quality of the deterministic solutions stemming from the 50th and the 75th percentile of the demand distributions. We then show that for all models, but in different ways, we are able to make effective use of parts of the deterministic solution, confirming the value of the deterministic solution in the stochastic environment, even when the deterministic solution itself performs badly. We also investigate what makes the optimal stochastic solution better in the stochastic environment than other feasible solutions, particularly those obtained by addressing deterministic versions of the problem. We do this by quantitatively analyzing the structures of different solutions. A measurement scheme is proposed to evaluate the level of potentially beneficial structural properties (multipath usage and path sharing) in different solutions. We show that these structural properties are important and correlated with the performance of a solution in the stochastic environment. Data and the online appendix are available at https://doi.org/10.1287/ijoc.2018.0819 .

City logistics seeks to optimize the distribution of goods in urban areas by developing new business models. Such models are not only centered on cost reduction, but also account for reducing the negative impact resulting from city logistics activities. Therefore, environmental aspects or congestion are important factors as well. Through consolidation of goods of different shipper-consignee pairs, the utilization of urban vehicles is improved and the total kilometers traveled within the city can be reduced. In the literature, inbound and outbound traffic are treated separately. This, however, results in empty urban vehicle traffic and reduces utilization of the system. Therefore, we consider a city logistics system that simultaneously accounts for both inbound and outbound demand. We consider a two-tier system, where the inbound goods are transported from external zones to satellites from where the final distribution is performed. The outbound demands are shipped via satellites to the external zones. To analyze the impact of considering both flows, we define and compare key performance indicators, like the urban vehicle utilization and number of vehicles. Numerical analyses are performed on different network structures and demand patterns. The results show the importance of combining both flows within one system. Moreover, we give insights on how different key performance indicators vary depending on the network and demand scenario.

Timing problems involve the choice of task execution dates within a predetermined processing sequence, and under various additional constraints or objectives such as time windows, time‐dependent costs, or flexible processing times, among others. Their efficient resolution is critical in branch and bound and neighborhood search methods for vehicle routing, project and machine scheduling, as well as in various applications in network optimization, resource allocation, and statistical inference. Timing‐related problems have been studied for years, yet research on this subject suffers from a lack of consensus, and most knowledge is scattered among operations research and applied mathematics domains. This article introduces a classification of timing problems and features, as well as a unifying multidisciplinary analysis of timing algorithms. In relation to frequent application cases within branching schemes or neighborhood searches, the efficient resolution of series of similar timing subproblems is also analyzed. A dedicated formalism of reoptimization “by concatenation” is introduced to that extent. The knowledge developed through this analysis is valuable for modeling and algorithmic design, for a wide range of combinatorial optimization problems with time characteristics, including rich vehicle routing settings and emerging nonregular scheduling applications, among others. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(2), 102–128 2015

Abstract We consider the stochastic fixed‐charge capacitated multicommodity network design (S‐CMND) problem with uncertain demand. We propose a two‐stage stochastic programming formulation, where design decisions make up the first stage, while recourse decisions are made in the second stage to distribute the commodities according to observed demands. The overall objective is to optimize the cost of the first‐stage design decisions plus the total expected distribution cost incurred in the second stage. To solve this formulation, we propose a metaheuristic framework inspired by the progressive hedging algorithm of Rockafellar and Wets. Following this strategy, scenario decomposition is used to separate the stochastic problem following the possible outcomes, scenarios, of the random event. Each scenario subproblem then becomes a deterministic CMND problem to be solved, which may be addressed by efficient specialized methods. We also propose and compare different strategies to gradually guide scenario subproblems to agree on the status of design arcs and aim for a good global design. These strategies are embedded into a parallel solution method, which is numerically shown to be computationally efficient and to yield high‐quality solutions under various problem characteristics and demand correlations. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011.

Abstract This article discusses problems in the context of multicommodity network design where 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 the penalized costs, these problems are generally in the form of a nonlinear integer multicommodity network design problem. This article presents two algorithms based on Lagrangean relaxation and decomposition for the solution of such problems. The first relies upon dualizing the capacity constraints that results in a flow decomposition, and the second is through relaxing flow constraints that results in an arc 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. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Addressing multi-attribute, ldquorichrdquo combinatorial optimization problems in a comprehensive manner presents significant methodological and computational challenges. In this paper, we present an integrative multi-thread cooperative optimization framework that can simultaneously deal with multiple dimensions of a rich problem. We present the basic concepts and detail the design and operating principles of the methodology. We illustrate the framework on a rich combinatorial problem, an extended version of the vehicle routing problem with the duration and capacity constraints as well as time windows, multiple periods and multiple depots.

One of the main issues in addressing three-dimensional packing problems is finding an efficient and accurate definition of the points at which to place the items inside the bins, because the performance of exact and heuristic solution methods is actually strongly influenced by the choice of a placement rule. We introduce the extreme point concept and present a new extreme point-based rule for packing items inside a three-dimensional container. The extreme point rule is independent from the particular packing problem addressed and can handle additional constraints, such as fixing the position of the items. The new extreme point rule is also used to derive new constructive heuristics for the three-dimensional bin-packing problem. Extensive computational results show the effectiveness of the new heuristics compared to state-of-the-art results. Moreover, the same heuristics, when applied to the two-dimensional bin-packing problem, outperform those specifically designed for the problem.

The demand-adaptive systems studied in this paper attempt to offer demand-responsive services within the framework of traditional scheduled bus transportation: Users call to request service between two given points and, in so doing, induce detours in the vehicle routes; at the same time, though, a given set of compulsory stops is always served according to a predefined schedule, regardless of the current set of active requests. The model developed to select requests and determine the routing of the vehicle yields a difficult formulation but with a special structure that may be used to develop efficient algorithms. In this paper, we develop, test, and compare several solution strategies for the single line-single vehicle problem that belong to two general meta-heuristic classes, memory-enhanced greedy randomized multistart constructive procedures, and tabu search methods. Hybrid meta-heuristics combining the two methods are also analyzed.

In this paper, we present a new methodology for the design of fault-tolerant logical topologies in wavelength-routed optical networks supporting Internet protocol (IP) datagram flows. Our design approach generalizes the "design protection" concepts, and relies on the dynamic capabilities of IP to reroute datagrams when faults occur, thus achieving protection and restoration, and leading to high-performance cost-effective fault-tolerant logical topologies. In this paper, for the first time we consider resilience properties during the logical topology optimization process, thus extending the optimization of the network resilience also to the space of logical topologies. Numerical results clearly show that our approach outperforms previous ones, being able to obtain very effective survivable logical topologies with limited computational complexity.

In this paper we illustrate a new methodology for the design of fault-tolerant logical topologies in wavelength-routed optical networks exploiting wavelength division multiplexing, and supporting both unicast and multicast IP datagram flows. Our approach to protection and restoration generalizes the "design protection" concepts, and relies on the dynamic capabilities of IP routing to re-route IP datagrams when faults occur, thus leading to high-performance cost-effective fault-tolerant logical topologies. Our design methodology for the first time considers the resilience properties or the topology during the logical topology optimization process, thus extending the optimization of the network resilience performance also on the space of the logical topologies. Numerical results clearly show that our approach is able to obtain very good logical topologies with limited complexity.

The fixed charge capacitated multicommodity network design problem is a well-known problem, of both practical and theoretical significance. This paper presents an efficient procedure to determine tight upper bounds on the optimal solution of realistically sized problem instances. Feasible solutions are obtained by using a tabu search framework that explores the space of the continuous flow variables by combining pivot moves with column generation, while evaluating the actual mixed integer objective. Computational experiments on a large set of randomly generated test problems show that this procedure outperforms the other available methods and is particularly suited to large problem instances with many commodities.

The search history of memory based heuristics like tabu search can be used to design a category of parallel algorithms, called cooperative search. These algorithms execute in parallel several search programs on the same optimization problem instance. At run time, the data gathered in the memory by one sequential search program need not be used only by this program, but it can be recycled and shared with other concurrently executing tabu search programs for the same purpose. In this paper we compare the global behavior of cooperating and non-cooperating tabu search programs. We show that cooperating programs tend to have a search pattern which is less diversified than non-cooperating programs. Our findings also indicate that this second order impact of the sharing of gathered data on the search behaviors of cooperating programs is not related to the optimization properties of the individual tabu programs.

In this paper we present a classification of parallel tabu search metaheuristics based, on the one hand, on the control and communication strategies used in the design of the parallel tabu search procedures, and on the other hand, on how the search space is partitioned. These criteria are then used to review the parallel tabu search implementations described in the literature. The taxonomy is further illustrated by the results of several parallelization implementations of a tabu search procedure for multicommodity location-allocation problems with balancing requirements.