Project topics and materials
Get Complete Project Material File(s) Now! »
Routing problems and bikes balancing problems
Routing problems gather operational problems faced in the management of distribution tasks. The field of transportation has been one of the major focus of the Operation Research (OR) community. The interest in this topic arose very early. At first, only the savings that can be achieved have motivated to better schedule transportation activities. Growing environment concerns have then enhanced the attractiveness of this field of research. The first and original problem studied is the well-known Travelling Salesman Problem (TSP). Signs of the TSP are found as early as the 1830s in Germany in [19], though this article contains no mathematical treatment. It was named after the problem faced by travelling salesmen who have to visit several cities and so to plan a closed trail – cycle. But to save time or money, they want to find the cycle that would be the less costly for them. The first trace of mathematicians’ interests for the TSP are in the 1930s when it seems to be studied both in Germany and the US. It became in the 1950s and 1960s a very popular topic for researchers.
In its formal definition, the objective is to plan a closed trail visiting once several cities while minimizing the total number of kilometers travelled. The distance matrix is given. In 1954, Dantzig et al. [29] presented the optimal cycle linking 49 American cities, one per state + Washington D.C.. They were the first to present a integer linear program and to propose a cutting plane method. This process was later extended with the introduction of branch-and-cut algorithms. In 1962, the society Procter and Gamble ran a contest for finding the optimal cycle reaching 33 American cities. With no surprise, American researchers in OR were listed among the winners. In 1962, Held and Karp [50] presented a dynamic programming approach that successfully solves small size instances. The TSP was proven to be NP-hard in 1972 after Karp proved the NP-completeness of finding an Hamiltonian cycle in a graph, where an Hamiltonian cycle in a graph is a closed trail that visits all vertices once. Since then, the size of instances optimally solved have increased to reach today optimal solution for almost 90′000 cities. Huge size instances come from very-large-scale integration problem where a huge amount of transistors have to be taken to put them into chips.
Other Vehicle Routing Problems (VRPs) have been defined since the Fifties. More complex than the TSP, they enabled to model and to study different real life transportation problems where other constraints appear. These different features lead to the definition of variants of the TSP, some of them are reported below. The asymmetric TSP is the same problem but where the distance matrix is asymmetric. In the sequential ordering problem, there are precedence constraints on the cities: some cities have to be visited before others.
In the Capacitated Vehicle Routing Problem (CVRP), a fleet of capacitated vehicles is available and to each cities – or customers – a demand is attached. The objective is to find the collection of closed trail such that every customer is visited once and that his demand is satisfied without exceeding the vehicle capacity. The CVRP first defined in [30] is one of the most studied variant on the TSP. It is a generalization of the TSP. Indeed, the TSP corresponds to an instance with a single vehicle available at the depot which capacity is greater than the sum over the demand of all customers, the depot being the initial city of the tour. Multiple variants exist on the CVRP or the TSP, adding complications on the tour of the vehicle. In the CVRP case, see [83] for a list of them. Here we give a list of some of them that are relevant with regard to this thesis.
– Associating time windows to customers restrains the visit to occur within time limits.
– Enabling the customers to be visited by several vehicles by splitting his demand.
– Having pickup or delivery operations at the vertices; objects have to be picked up or delivered at vertices. It could be the same or different commodities.
Split means that the demands may be satisfied by several vehicles. The Split Delivery VRP (SDVRP) was first introduced by Dror and Trudeau [35]. As in the CVRP, each customer has a demand that has to be served by capacitated vehicles that are parked at a depot. But vehicles can serve only part of the demand of a customer. Dror and Trudeau proved that the split dimension of the problem could lead to huge savings in term of the objective function [34]. The split component of the problem increases the complexity of the algorithm [8]. However, they found a property that limits the number of solutions to consider. If the costs satisfy the triangle inequality, then there exists an optimal solution to the SDVRP where no two routes have more than one customer with a split delivery in common. Having pickup and delivery requests at vertices leads to different problems depending on specific characteristics. Laporte et al. [15] sort the different Pickup and Delivery Problems (PDPs) that were introduced by different authors. They are sorted with respect to how pickup and delivery vertices are paired or not. Here we will focus on the many-to-many problems.
Many-to-many means that pickup and delivery points are not paired. An object picked up at a vertex can be delivered to any other vertex that has a demand for this type of object. Three different problems are in this class.
In the swapping problem, a single vehicle has to move unitary objects from a vertex to another. There are m different types of objects and the vehicle has a unitary capacity: it can only move one object at the time. Each vertex is associated with the type of object currently present at it, if any, and the desired object type, if any. For each type of object, the total demand is assumed to be equal to the total supply. The objective is to find a tour for a unique unit capacity vehicle at the end of which all objects are brought at a vertex where there is a request for an object of their type. This problem was introduced by Anily and Hassin in [6]. They showed that a vertex could be visited at most three times in the optimal solution. The problem has a preemptive version and a non-preemptive version. In the preemptive version, an object can be dropped at a vertex that is not its destination vertex to be collected later on by the vehicle when it comes back.
The second problem in this category is the One-Commodity Pickup-and-Delivery Travelling Salesman Problem (1PDTSP). It was first introduced by Hernández-Pérez and Salazar- González in [66]. Vertices are divided into pickup and delivery vertices. There is only one type of commodity. To each vertex is associated a non-zero demand, that is the amount of the commodity to either pickup or deliver at the corresponding customer, respectively to its sign. A capacitated vehicle is given at a depot. The objective is to find the minimum Hamiltonian tour that visits once each customer and brings the commodities from pickup vertices to delivery ones. This Hamiltonian tour has to respect the capacity of the vehicle.
The Q-Delivery Travelling Salesman Problem (Q-DTSP) is a special case of the 1PDTSP where all the demands are unit demands. In this case, the demand at pickup or delivery vertices is only one unit of the commodity. It was introduced before the latter in 1999 by Motwani and Chalasani in [63]. Here again, the solution is an Hamiltonian tour. They propose an approximation algorithm to solve it. The same problem was studied at the same time by Anily and Bramel. In [5] they introduce the Capacitated Travelling Salesman Problem with Pickup and Delivery (CTSPPD) as an extension of the swapping problem with one commodity and a capacitated vehicle.
Literature review
In the literature, similar problems are the One-commodity Pickup-and-Delivery Travelling Salesman Problem (1PDTSP) studied by Hernandez Pérez and Salazar González [67] and the swapping problem defined by Anily and Hassin [6]. This latter has been solved by [20, 47] in its preemptive and its non-preemptive versions. As for the 1PDTSP, several papers have been appeared recently in the literature which propose different exact and heuristic algorithms (see [68], [69] and [70]). Since these two problems present several similarities with our problem, more details about them are given in the next paragraph. Raviv et al. [76] discuss different variants of the problem of repositioning the bikes which are modeled by mixed linear programs and solved using CPLEX. For some variants, they are able to solve several instances to optimality (up to 60 stations and 2 vehicles for their so-called “Arc-Indexed” variant). Our model is close to their “Sequence-Indexed” variant (see Section 3.4 of [76]), but instead of computing a minimum cost route with fixed target states, they try to find the best repartition of bikes that can be achieved by one or several vehicles within a time limit. Moreover, in the Sequence Index formulation given by [76], drops are not allowed, a thing that will be fixed in an upcoming version by [75].
The SVOCPDP gathers aspects from both the swapping problem and the 1PDTSP but differs by main features. In the swapping problem, a single vehicle has to move unitary objects from a vertex to another. There are m different types of objects and the vehicle has a unitary capacity: it can only move one object at the time. Shoshana Anily and Refael Hassin [6] showed that a vertex could be visited at most three times in the optimal solution. This theorem was the starting point of the work of Bordenave et al. [20, 47] for solving the swapping problem with a branch-and-cut algorithm. The SVOCPDP is different since there is only one type of object (bikes), but the supply and the demand are greater than one and the vehicle capacity is K. Therefore, Anily and Hassin’s theorem does not hold anymore: for example in the trivial instance with one pickup vertex with pi = 5K and qi = 0 and one delivery vertex with pi = 0 and qi = 5K, the vehicle has to do five round trips between the two vertices. The main difference with the 1PDTSP is that in the SVOCPDP a vertex can be visited several times. The solution of the 1PDTSP is a feasible solution for the SVOCPDP, but the SVOCPDP can have a lower-cost optimal solution. Moreover, the 1PDTSP may have instances without feasible solutions (the instance of Figure 2.3, with K = 3, is an example), something that can not happen for the SVOCPDP.
The fact that one can get better solutions in routing problems when customers are allowed to be visited several times has already be noticed in other works. Note for instance the work by Archetti et al. [7], in which a split delivery problem is solved through a tabu search. In the problem we are dealing with any vertex can be used as a buffer where bikes can be indifferently temporary loaded or unloaded before being moved to their final destination. In particular, initially balanced vertices are not required to be visited, but may act as temporary depot in some optimal solutions.
The buffers can improve the optimal solution in some instances such as shown in the example given in Figure 2.3 and in Figure 2.5. In Figure 2.3 the square with the 0 inside is the depot and its distance with vertex 1 is null. For any other vertex i, (pi; qi) is given. The capacity of the vehicle is K = 3 and the distances between all the peripheral vertices to the central one is 1. We draw here the optimal solution, whose value is equal to 10. In this solution a bike is temporary unloaded at the central vertex 6 and then reloaded on the vehicle. The optimal solution is equal to 12, if drop is forbidden because one of the odd number vertices would have to be visited twice.
Dealing with sequences and routes
Recall that a route is a sequence of vertices, together with bike displacements within the limits of capacity constraints, at the end of which the system is balanced: each vertex i has been brought from its initial state pi to its final state qi. The difficulty of the SVOCPDP is that a feasible solution is identified by both a sequence of vertices and a set of numbers of bikes carried on arcs. The following proposition (and its companions Propositions 2.3.2 and 2.3.3) enables us to work only with sequences of vertices. It will be particularly useful in Section 2.8 when we will design a local search for the SVOCPDP.
Table of contents :
1 Introduction
1.1 Bike sharing system
1.2 Research motives
1.3 Routing problems and bikes balancing problems
1.4 Thesis overview
2 Solving the Single-Vehicle One-commodity Capacitated Pickup and Delivery Problem
2.1 Introduction
2.1.1 Complexity
2.1.2 Notations and basic notions
2.1.3 Plan
2.2 Literature review
2.3 Dealing with sequences and routes
2.4 An exact model
2.5 Relaxations
2.5.1 A first relaxation
2.5.2 A second relaxation
2.6 Relaxation vs original problem
2.7 Lower bound
2.7.1 Separation of connectivity constraints
2.7.2 Separation of capacity constraints
2.7.3 Initial relaxation, separation strategy and branching rules
2.8 Upper bound
2.8.1 Cost of the current solution
2.8.2 Initial solution
2.8.3 Neighborhood description
2.8.4 The tabu list
2.8.5 The tabu search
2.9 Computational study
2.9.1 Instances
2.9.2 Computational results
2.9.3 Conclusion
3 The Multiple-Vehicle Balancing Problem
3.1 Introduction
3.2 Problem and notations
3.2.1 Problem definition
3.2.2 Notations
3.3 Literature
3.4 Dominance properties, model and method
3.4.1 Dominance properties
3.4.2 The model
3.4.3 Method
3.5 Relaxation
3.6 Solving the pricing subproblem
3.6.1 The GENPATH procedure
3.6.2 The GENROUTE procedure
3.6.3 Additional dominance rules in GENPATH
3.6.4 Lower bound lb for GENPATH
3.7 Adding cuts to increase the z(RSPF)
3.7.1 Dual-feasible function cuts
3.7.2 Dominances cuts
3.8 Upper bound
3.8.1 Individuals
3.8.2 Score of an individual
3.8.3 Cross-Over Operation
3.8.4 Local searches
3.8.5 Population and selection
3.8.6 MA calls in the overall algorithm
3.9 Computational study
3.9.1 Instances and results
3.9.2 Conclusion
4 Real-time shared transport system: model and simulations
4.1 Introduction
4.2 Shared transport system: the model
4.2.1 Transportation equipment
4.2.2 Users behaviour
4.3 Description of the simulator
4.3.1 Evaluation of the quality of the management
4.4 Conclusion
5 Real time optimization methods
5.1 Introduction
5.2 Methods using trucks
5.2.1 Preliminaries
5.2.2 One-step – two-step heuristics
5.2.3 One-step – two-step heuristics with forecast
5.2.4 The Colored Cluster heuristic
5.3 Methods using incentive policy
5.4 Computational study
5.4.1 Instances
5.4.2 Results
5.4.3 Discussion
5.5 Conclusion
6 The Initial Inventory Problem
6.1 Introduction
6.2 Initial Inventory Problem
6.3 Finding the optimal initial inventory
6.3.1 Time driven search
6.3.2 Occurrence driven search
6.4 Results
6.5 Conclusion
7 Conclusion
A Challenge ROADEF 2010: Solving electricity production planning by column generation
A.1 Introduction
A.2 Problem statement
A.3 Compact formulation
A.4 Decomposition and solution method
A.4.1 Decomposition
A.4.2 Solution method
A.5 Solving the pricing problem
A.5.1 Creation of a static graph
A.5.2 Weighting the arcs of a graph
A.5.3 Obtaining dual variables μw and ui
A.6 Solving the final master problem
A.7 Columns diversification
A.8 Calculate the reload and the production quantities
A.8.1 LP-solving for fixing reload quantities
A.8.2 Disaggregate LP-solving for every scenario and initial time steps
A.9 Computational results
A.9.1 Instances
A.9.2 Results and discussion
A.10 Conclusion
B Challenge ROADEF 2012: Machine Assignment Problem
B.1 The model
B.2 The method
B.3 The results
