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
2614461528 1998816621 2176306573 2121266360
Optimizing shared vehicle systems (bike-sharing car-sharing ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of complex network externalities. In particular, changes in the demand supply at any location (via dynamic pricing, rebalancing of empty vehicles, etc.) affect future supply throughout the system within short timescales. Such externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze and design shared vehicle systems. However, using such models to design pricing control policies is computationally difficult since the resulting optimization problems are high-dimensional and non-convex. To this end, we develop a general approximation framework for designing pricing policies in shared vehicle systems, based on a novel convex relaxation which we term elevated flow relaxation. Our approach provides the first efficient algorithms with rigorous approximation guarantees for a wide range of objective functions (throughput, revenue, welfare). For any shared vehicle system with @math stations and m vehicles, our framework provides a pricing policy with an approximation ratio of 1+(n-1) m. This guarantee is particularly meaningful when m n, the average number of vehicles per station is large, as is often the case in practice. Further, the simplicity of our approach allows us to extend it to more complex settings. Apart from pricing, shared vehicle systems enable other control levers for modulating demand and supply, e.g. rebalancing empty vehicles, redirecting riders to nearby vehicles, etc. Our approach yields efficient algorithms with the same approximation guarantees for all these problems, and in the process, obtains as special cases several existing heuristics and asymptotic guarantees. We also extend our approach to obtain bi-criterion guarantees in multi-objective settings; we illustrate this with the example of Ramsey pricing. From a technical perspective, our work develops a new approach for obtaining control policies with approximation guarantees in steady-state Markovian models. Our approach can be distilled into the following three-step program: (i) construct an upper bound via a relaxation to the original problem that encodes essential conservation laws of the system, (ii) identify a family of control policies inducing known steady-state distributions that achieve the value of the relaxed solution in an appropriate scaling limit (in our case, state-independent policies in the limit m++), and (iii) characterize the performance loss between the finite system (i.e. fixed m) and the scaling limit. This technique may be of independent interest for other settings. The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15 . Moreover, improvements of up to 41 can be achieved for some test instances. 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. We consider an inventory routing problem in discrete time where a supplier has to serve a set of customers over a multiperiod horizon. A capacity constraint for the inventory is given for each customer, and the service cannot cause any stockout situation. Two different replenishment policies are considered: the order-up-to-level and the maximum-level policies. A single vehicle with a given capacity is available. The transportation cost is proportional to the distance traveled, whereas the inventory holding cost is proportional to the level of the inventory at the customers and at the supplier. The objective is the minimization of the sum of the inventory and transportation costs. We present a heuristic that combines a tabu search scheme with ad hoc designed mixed-integer programming models. The effectiveness of the heuristic is proved over a set of benchmark instances for which the optimal solution is known.