We propose exact solution approaches for a lateral transhipment problem which, given a pre-specified sequence of customers, seeks an optimal inventory redistribution plan considering travel costs and profits dependent on inventory levels. Trip-duration and vehicle-capacity constraints are also imposed. The same problem arises in some lot sizing applications, in the presence of setup costs and equipment re-qualifications. We introduce a pure dynamic programming approach and a branch-and-bound framework that combines dynamic programming with Lagrangian relaxation. Computational experiments are conducted to determine the most suitable solution approach for different instances, depending on their size, vehicle capacities and duration constraints. The branch-and-bound approach, in particular, solves problems with up to 50 delivery locations in less than ten seconds on a modern computer.
Other related problems have been defined on a single planning period, such as the TSP with pickups and deliveries @cite_4 , the balancing problems for static bike sharing systems @cite_10 @cite_3 and also the lateral transhipment problem for a single route (SRLTP), @cite_1 @cite_11 . This latter problem aims to distribute inventory on a network @math via pickups and deliveries using one vehicle, to minimize a non-linear objective. In bike sharing systems @cite_2 , a target level is defined and the objective is to minimize the corresponding total deviation (a piecewise-linear convex function). Some MIP formulations of this problem are introduced in @cite_23 . The objective includes expected shortage costs and travel costs, similar to the TSP with profits @cite_29 . Dynamic route interactions like hand-overs (intermediate storage) and multiple visits are also considered.
@cite_4 @cite_29 @cite_1 @cite_3 @cite_23 @cite_2 @cite_10 @cite_11
2031736545 1991149726 1921393379 2032251915 2145656012 2176306573
We study a generalization of the well-known traveling salesman problem (TSP) where each customer provides or requires a given non-zero amount of product, and the vehicle in a depot has a given capacity. Each customer and the depot must be visited exactly once by the vehicle supplying the demand while minimizing the total travel distance. We assume that the product collected from pickup customers can be delivered to delivery customers. We introduce a 0-1 integer linear model for this problem and describe a branch-and-cut procedure for finding an optimal solution. The model and the algorithm are adapted to solve instances of TSP with pickup and delivery. Some computational results are presented to analyze the performance of our proposal. Traveling salesman problems with profits (TSPs with profits) are a generalization of the traveling salesman problem (TSP), where it is not necessary to visit all vertices. A profit is associated with each vertex. The overall goal is the simultaneous optimization of the collected profit and the travel costs. These two optimization criteria appear either in the objective function or as a constraint. In this paper, a classification of TSPs with profits is proposed, and the existing literature is surveyed. Different classes of applications, modeling approaches, and exact or heuristic solution techniques are identified and compared. Conclusions emphasize the interest of this class of problems, with respect to applications as well as theoretical results. We consider the necessary redistribution of bicycles in public bicycle sharing systems in order to avoid rental stations to run empty or entirely full. For this purpose we propose a general Variable Neighborhood Search (VNS) with an embedded Variable Neighborhood Descent (VND) that exploits a series of neighborhood structures. While this metaheuristic generates candidate routes for vehicles to visit unbalanced rental stations, the numbers of bikes to be loaded or unloaded at each stop are efficiently derived by one of three alternative methods based on a greedy heuristic, a maximum flow calculation, and linear programming, respectively. Tests are performed on instances derived from real-world data and indicate that the VNS based on a greedy heuristic represents the best compromise for practice. In general the VNS yields good solutions and scales much better to larger instances than two mixed integer programming approaches. Bike-sharing systems allow people to rent a bicycle at one of many automatic rental stations scattered around the city, use them for a short journey and return them at any station in the city. A crucial factor for the success of a bike-sharing system is its ability to meet the fluctuating demand for bicycles and for vacant lockers at each station. This is achieved by means of a repositioning operation, which consists of removing bicycles from some stations and transferring them to other stations, using a dedicated fleet of trucks. Operating such a fleet in a large bike-sharing system is an intricate problem consisting of decisions regarding the routes that the vehicles should follow and the number of bicycles that should be removed or placed at each station on each visit of the vehicles. In this paper, we present our modeling approach to the problem that generalizes existing routing models in the literature. This is done by introducing a unique convex objective function as well as time-related considerations. We present two mixed integer linear program formulations, discuss the assumptions associated with each, strengthen them by several valid inequalities and dominance rules, and compare their performances through an extensive numerical study. The results indicate that one of the formulations is very effective in obtaining high quality solutions to real life instances of the problem consisting of up to 104 stations and two vehicles. Finally, we draw insights on the characteristics of good solutions. Bike-sharing is a new form of sustainable urban public mobility. A common issue observed in bike-sharing systems is imbalances in the distribution of bikes. There are two logistical measures alleviating imbalances: strategic network design and operational repositioning of bikes. IT-systems record data from Bike Sharing Systems (BSS) operation that are suitable for supporting these logistical tasks. A case study shows how Data Mining applied to operational data offers insight into typical usage patterns of bike-sharing systems and is used to forecast bike demand with the aim of supporting and improving strategic and operational planning. Previous research has analyzed deterministic and stochastic models of lateral transhipments between different retailers in a supply chain. In these models the analysis assumes given fixed transhipment costs and determines under which situations (magnitudes of excess supply and demand at various retailers) the transhipment is profitable. However, in reality, these depend on aspects like the distance between retailers or the transportation mode chosen. In many situations, combining the transhipments may save transportation costs. For instance, one or more vehicle routes may be used to redistribute the inventory of the potential pickup and delivery stations. This can be done in any sequence as long as the vehicle capacity is not violated and there is enough load on the vehicle to satisfy demand. The corresponding problem is an extension of the one-commodity pickup and delivery traveling salesman and the pickup and delivery vehicle routing problem. When ignoring the routing aspect and assuming given fixed costs, transhipment is only profitable if the quantities are higher than a certain threshold. In contrast to that, the selection of visited retailers is dependent on the transportation costs of the tour and therefore the selected retailers are interrelated. Hence the problem also has aspects of a (team) orienteering problem. The main contribution is the discussion of the tour planning aspects for lateral transhipments which may be valuable for in-house planning but also for price negotiations with external contractors. A mixed integer linear program for the single route and single commodity version is presented and an improved LNS framework to heuristically solve the problem is introduced. Furthermore, the effect of very small load capacity on the structure of optimal solutions is discussed.