Multi-location transshipment problem with capacitated production

We consider coordination among stocking locations through replenishment strategies that explicitly take into account lateral transshipments, i.e., transfer of a product among locations at the same echelon level. Our basic contribution is the incorporation of supply capacity into the traditional transshipment model. Our goal is to analyze the impact on system behavior and on stocking locations’ performance of the fact that the supplier may fail to fulfill all the replenishment orders. We therefore formulate the capacitated supply scenario as a network flow problem embedded in a stochastic optimization problem, which is solved through a sample average approximation method. We find that, depending on the production capacity, system behavior can vary drastically. Moreover, in a production-inventory system, we find evidence that either capacity flexibility (i.e., extra production) or transshipment flexibility (i.e., pooling) is required to maintain a desired level of service.     

Optimal expansion of capacitated transshipment networks

In this paper, we address the problem of allocating a given budget to increase the capacities of arcs in a transshipment network to minimize the cost of flow in the network. The capacity expansion costs of arcs are assumed to be piecewise linear convex functions. We use properties of the optimum solution to convert this problem into a parametric network flow problem. The concept of optimum basis structure is used which allows us to consider piecewise linear convex functions without introducing additional arcs. The resulting algorithm yields an optimum solution of the capacity expansion problem for all budget levels less than or equal to the given budget. For integer data, the algorithm performs almost all computations in integers. Detailed computational results are also presented.     

Solving the robust two-stage capacitated facility location problem with uncertain transportation costs

In this study, we start from a multi-source variant of the two-stage capacitated facility location problem (TSCFLP) and propose a robust optimization model of the problem that involves the uncertainty of transportation costs. Since large dimensions of the robust TSCFLP could not be solved to optimality, we design a memetic algorithm (MA), which represents a combination of an evolutionary algorithm (EA) and a modified simulated annealing heuristic (SA) that uses a short-term memory of undesirable moves from previous iterations. A set of computational experiments is conducted to examine the impact of different protection levels on the deviation of the objective function value. We also investigate the impact of variations of transportation costs that may occur on both transhipment stages on the total cost for a fixed protection level. The obtained results may help in identifying a sustainable and efficient strategy for designing a two stage capacitated transportation network with uncertain transportation costs, and may be applicable in the design and management of similar transportation networks.     

Primal transportation and transshipment algorithms

Summary Capacitated transshipment problems constitute the most general class of single commodity network flow problems. During the last ten years the emphasis has shifted away from the primal-dual solution methods back to specializations of the primal simplex algorithm as the more efficient approach. In this survey numerous variations in data structures, selection rules and implementations of individual steps are extracted from the relevant literature. The exposition is centered around one basic algorithm which is explained in complete detail with particular attention to the intricacies of the basis exchange part. Specialized solution methods for transportation and assignment problems are taken into account.

---

Zusammenfassung Die kapazitierten Transshipmentprobleme bilden die allgemeinste Klasse von Flußproblemen in Netzwerken, die sich mit der Verteilung einer einzigen Ware beschäftigen. Während der letzten zehn Jahre hat sich die Betonung von den primal-dualen Lösungsmethoden zurückverlagert zu den Spezialisierungen des primalen Simplexalgorithmus als der effizienteren Prozedur. Für diesen Übersichtsartikel werden die zahlreichen Variationen in den Datenstrukturen, in den Auswahlregeln und in den Verwirklichungen der einzelnen Schritte aus der entsprechenden Literatur ausgewählt. Die Ausführungen haben als Mittelpunkt einen Algorithmus, der in allen Einzelheiten erklärt wird, wobei den Schwierigkeiten des Basiswechsels besondere Aufmerksamkeit gewidmet wird. Spezielle Lösungsmethoden für Transport- und Zuordnungsprobleme werden mitberücksichtigt.

---

---

An invited survey.     

Implementation and analysis of a variant of the dual method for the capacitated transshipment problem

This paper presents a variant of the dual simplex method for the capacitated pure network problem and a computational analysis of this algorithm. This work includes the considerations of different list structures to store the original problem data and the basis and the testing of various procedures to select the leaving basic variable. This study also examines the sensitivity of the implementation to changes in problem parameters. The results show that the algorithm which is presented here is superior to earlier dual implementations.     

Periodic capacitated arc-routing problem with inventory constraints

The purpose of this paper is to study the periodic arc-routing problem when the arcs of a network behave as customers, and sufficient material is delivered so that each achieves its desired inventory level. Therefore, routing and inventory decisions are made simultaneously. Applications include dust suppression in open-pit mines or forest roads and plant watering along sidewalks or street medians. A truck periodically sprays water along the edges of a network. The humidity reaches a desired level and is then consumed over time until water is delivered again. The quantity of water delivered can be fixed or variable; we consider both scenarios and propose a mathematical model for each. Results are reported to validate the model. The contribution of this paper is the first mathematical model that combines inventory and routing decisions in the arc-routing domain.     

The capacitated arc routing problem with refill points

This article introduces the capacitated arc routing problem with refill points (CARP-RP). The vehicle servicing arcs must be refilled on the spot by using a second vehicle. The problem consists on simultaneously determining the vehicles routes that minimize the total cost. An integer linear programming model is proposed and tested.     

Solving the capacitated lot-sizing problem with backorder consideration

In this research, we formulate and solve a type of the capacitated lot-sizing problem. We present a general model for the lot-sizing problem with backorder options, that can take into consideration various types of production capacities such as regular time, overtime and subcontracting. The objective is to determine lot sizes that will minimize the sum of setup costs, holding cost, backorder cost, regular time production costs, and overtime production costs, subject to resource constraints. Most existing formulations for the problem consider the special case of the problem where a single source of production capacity is considered. However, allowing for the use of alternate capacities such as overtime is quite common in many manufacturing settings. Hence, we provide a formulation that includes consideration of multiple sources of production capacity. We develop a heuristic based on the special structure of fixed charge transportation problem. The performance of our algorithm is evaluated by comparing the heuristic solution value to lower bound value. Extensive computational results are presented.     

The capacitated team orienteering problem with incomplete service

In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service.     

The capacitated max k-cut problem

We consider a capacitated max k-cut problem in which a set of vertices is partitioned into k subsets. Each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that maximizes the sum of edge weights across all pairs of vertices that lie in different subsets. We describe a local-search algorithm that obtains a solution with value no smaller than 1 − 1/k of the optimal solution value. This improves a previous bound of 1/2 for the max k-cut problem with fixed, though possibly different, sizes of subsets. We thank an anonymous referee for extensive and constructive comments. The first and second authors are grateful for the support provided by the Natural Sciences and Engineering Research Council of Canada.     

Solving the capacitated location-routing problem

This is a summary of the main results presented in the author’s Ph.D thesis, available at http://prodhonc.free.fr/homepage. This thesis, written in French, was supervised by Christian Prins and Roberto Wolfler-Calvo, and defended on 16 October 2006 at the Université de Technologie de Troyes. Several new approaches are proposed to solve the capacitated location-routing problem (CLRP): heuristic, cooperative and exact methods. Their performances are tested on various kinds of instances with capacitated vehicles and capacitated or uncapacitated depots.      

New mixed integer-programming model for the pickup-and-delivery problem with transshipment

In recent years, many important real-world applications are studied as “rich” vehicle routing problems that are variants and generalizations of the well-known vehicle routing problem. In this paper we address the pickup-and-delivery version of this problem and consider further generalization by allowing transshipment in the network. Moreover, we allow heterogenous vehicles and flexible fleet size. We describe mixed integer-programming formulations for the problem with and without time windows for services. The number of constraints and variables in the models are bounded by polynomial size of the problem. We discuss several problem variants that are either captured by our models or can be easily captured through simple modifications. Computational work gave promising results and confirms that transshipment in network can indeed enhance optimization.     

Two-stage stochastic modeling of transportation outsourcing plans for transshipment centers

In this study, we deal with the problem of short-term transportation outsourcing for transshipment centers. The carrier needs to determine the numbers of outsourced and self-run trips for the different types of transportation tasks. Stochastic demands which are likely to occur in actual operation are considered. Different trip numbers need to be determined in sequence, so a two-stage stochastic programming technique is applied to formulate the problem. Two models are developed based upon practical considerations to help determine the optimal transportation outsourcing plan. A case study regarding the operations of a logistics carrier in Taiwan is performed. Several tests are also performed considering the number of demand scenarios, optimality gaps, variations in demands, outsourcing cost variations, and problem dimensions in order to better understand the performance of the two models.     

The periodic capacitated arc routing problem with irregular services

The aim of this paper is to introduce the periodic capacitated arc routing problem with irregular services. Some applications can be found in road maintenance operations and road network surveillance. The problem consists of determining a set of routes to cover a given network over a time horizon. The roads must be serviced a number of times in sub-periods over the time horizon, according to a hierarchy of arc classes. We present a mathematical model and a heuristic solution approach.     

The capacitated maximal covering location problem with backup service

The maximal covering location problem has been shown to be a useful tool in siting emergency services. In this paper we expand the model along two dimensions — workload capacities on facilities and the allocation of multiple levels of backup or prioritized service for all demand points. In emergency service facility location decisions such as ambulance sitting, when all of a facility's resources are needed to meet each call for service and the demand cannot be queued, the need for a backup unit may be required. This need is especially significant in areas of high demand. These areas also will often result in excessive workload for some facilities. Effective siting decisions, therefore, must address both the need for a backup response facility for each demand point and a reasonable limit on each facility's workload. In this paper, we develop a model which captures these concerns as well as present an efficient solution procedure using Lagrangian relaxation. Results of extensive computational experiments are presented to demonstrate the viability of the approach.     

The capacitated general windy routing problem with turn penalties

In this paper we present the capacitated general windy routing problem with turn penalties. This new problem subsumes many important and well-known arc and node routing problems, and it takes into account turn penalties and forbidden turns, which are crucial in many real-life applications, particularly in downtown areas and for large vehicles. We provide a way to solve this problem both optimally and heuristically by transforming it into a generalized vehicle routing problem.     

The pyramidal capacitated vehicle routing problem

This paper introduces the pyramidal capacitated vehicle routing problem (PCVRP) as a restricted version of the capacitated vehicle routing problem (CVRP). In the PCVRP each route is required to be pyramidal in a sense generalized from the pyramidal traveling salesman problem (PTSP). A pyramidal route is defined as a route on which the vehicle first visits customers in increasing order of customer index, and on the remaining part of the route visits customers in decreasing order of customer index.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.