|
Article Excerpt
1. Introduction
The Single-Vehicle Routing Problem with Fixed Delivery and Optional Collections (or simply the delivery-optional collections problem) was introduced by Sural and Bookbinder (2003). In this problem, a set of customers, the "delivery customers," receive goods from a depot. These customers must be visited, in no preset order, by a vehicle. The vehicle must have enough capacity to carry all the goods that need to be distributed to these customers. There is also a set of "collection customers." Each collection customer must send goods to the depot; however, their goods are collected within the delivery trip only if it helps avoiding costs that would be incurred if the collection customer, or a third-party delivery service, had delivered the goods and charged for their movement. The goods of each individual collection customer are either fully collected or not collected at all. The goal is to find an optimal route for the vehicle such that, starting and ending at the depot, it minimizes the costs associated with visiting all delivery customers once cost avoidance - the cost savings resulting from visiting collection customers - is factored in. The capacity of the vehicle must never be exceeded. The solution to the problem determines which collection customers are to be visited. This is an NP-hard problem, since for null savings resulting from visiting the collection customers, it reduces to the Traveling Salesman Problem (TSP).
An example of this problem is a manufacturing or food company that must distribute its products daily using a vehicle. Spare parts and supplies for this company are provided by different small vendors. If the vehicle used for delivery also visits these suppliers, there are savings; if the savings are larger than the cost of visiting the supplier, then this supplier's goods are collected. Every day, the vehicle must follow a route that depends on which delivery and collection customers are to be visited.
In spite of the practical importance of this problem, it has only been addressed by Sural and Bookbinder (2003). They formulated this problem using flow variables and adaptations of the well-known Miller-Tucker-Zemlin constraints (Miller et al., 1960) in order to preclude subtours, and used a branch-and-bound technique as the solution method. They found solutions for instances of up to 30 customers.
Although results on the delivery-optional collections problem are scant, a review of the recent literature on related problems sheds some light on possible solution methods for it. A very similar problem is the TSP with Delivery and Collections. In this problem, there arc also delivery and collection customers, but all of them must be visited by the vehicle. Baldacci et al. (2003) proposed an exact method for solving this problem. The multiple-vehicle version of this problem is the Vehicle Routing Problem with Backhauls (VRPB), in which each vehicle can either visit both types of customers or only one type of client. For vehicles visiting both types of customers, the tours must be constructed in such a way that each vehicle is forced to visit its assigned delivery customers first, and its collection customers subsequently. Exact solutions have been found by Toth and Vigo (1997) and Mingozzi et al. (1999). Several methods have also been offered by Yano et al. (1987). Goetschalckx and Jacobs-Blecha (1989), Brandao (2006) and Ropke and Pisinger (2006). There are also several variations of the VRPB. Tavakkoli-Moghaddam et al. (2006) considered a non-homogeneous vehicle fleet; Wade and Salhi (2002) relaxed the requirement of having to visit the delivery customers first, and solved the problem assuming that a certain proportion of the load must be delivered before serving collection customers. Mosheiov (1998) relaxed this requirement completely, allowing the optimization model to determine whom to visit first while considering the vehicle capacity constraints.
Gribkovskaia et al. (2007) used Tabu Search for solving a problem that is a variation of the TSP with Delivery and Collections, in which each customer can be visited once or twice. Bianchessi and Righini (2007) solved a multiple-vehicle version of this problem in which customers receive and ship out loads during the same visit.
It is worth mentioning that in practice, any problem considering both delivery and collections involves making decisions not only about the route that the vehicle will follow, but also about how the vehicle will be loaded. For example, if the vehicle is a truck that is loaded from the back, some of the items will possibly need to be unloaded before loading new ones. In this case, a strategy is to leave some open space so that load movements do not become too complicated. However, note that the loading-unloading problem is highly dependent on the practical situation, type of industry and product. For instance, if the vehicle takes employees home after a shift, it can also pick up some employees for the next shift. In this example there is no loading-unloading problem, but only a capacity problem; in contrast, if the truck is carrying furniture (distributing to customers and picking up from providers), the situation is very different. In this paper, we follow the mainstream of the published literature in not attempting to address loading-unloading issues.
Cost avoidance resulting from visiting collection customers could be seen as profit. One profit-seeking routing problem is the Orienteering Problem (OP), which identifies a tour to visit the most profitable customers, when there is only one type of customer and a limit on the length or on total time of the tour. Its multiple vehicle version is the Team Orienteering Problem and a multiple-objective variant exists that minimizes the length of the tour or tours and maximizes the profit from visiting customers. Feillet et al. (2005) and Tang and Miller-Hooks (2005) have provided good literature reviews. These problems have been solved using heuristics by Ke et al. (2008) and Vansteenwegen et al. (2009) and using exact methods in Laporte and Martello (1990), Fischetti et al. (1998) and Berube et al. (2008).
Branch-and-cut procedures have been applied successfully to several problems, including some of those described above. For example, Lu and Dessouky (2004) and Cordeau (2006) solved the multiple vehicle version of the TSP with Pickup and Delivery, also called the Dial-a-Ride problem, in which the vehicles pick-up goods at one customer's location and deliver these goods to another customer. These authors used the Miller-Tucker-Zemlin constraints in their formulations. The same problem was solved by Hernandez and Salazar (2004), who used continuous variables representing the load being carried on each edge of the network, as well as binary edge variables. Baldacci et al. (2003) used a branch-and-cut approach to solve the TSP with Delivery and Collections. Their formulation had one set of flow variables for delivery and another one for collections. Gendreau et al. (1998) solved the Selective TSP, a version of the OP with compulsory visits to a subset of customers, using edge and choice variables.
Our contribution is a branch-and-cut procedure for the delivery-optional collections problem. The integer programming formulation of this problem is new; it includes both a constraint that explicitly precludes tours exceeding the capacity of the vehicle, and a subtour breaking constraint that avoids tours that do not include the depot node. In the branch-and-cut procedure, these constraints are relaxed and used to formulate adequate cuts. As a consequence, the problem solved at each node of the branch-and-cut procedure has a small number of constraints, which makes the procedure faster. We use a known cut (Gendreau et al., 1998) and find two new cuts, which for the first time deal with the presence of two types of customers, of which one type does not require compulsory visits. Finally, we propose a new separation algorithm that is faster and more efficient than the TSP separation algorithm normally used (which solves a set of maximal flow problems between a node and all remaining nodes). This method allows us to solve in less time all instances for which Sural and Bookbinder (2003) found an optimal solution, and also permits solving larger instances of the problem. We provide computational experience for up to 90 customers.
The remainder of the paper is organized as follows. In Section 2, we define the notation and propose the model for the delivery-optional collections problem. In Section 3, we present the new cuts and prove their validity. In Section 4, the branch-and-cut method is described. Our computational experience is reported in Section 5. We end with conclusions in Section 6.
2. The model
We represent our geographical setting as an undirected graph G = (N, E). The depot and both types of customers, delivery and collection, are located on nodes of the graph. The depot node is denoted [n.sub.0]; the set D contains all nodes representing delivery customers and the set C contains the nodes representing collection customers. Then, the set N is N= D [union] C [union] {[n.sub.0]}. Following Sural and Bookbinder (2003), we address the case in which delivery and collection node sets are disjoint. However, customers that receive and send goods can be easily included, as we discuss after presenting the model.
Every edge (i, j) of the graph is a potential leg of the tour described by the vehicle. Routes are formed by connecting edges. If a route begins and ends at the same node, the route is a tour. Let [[alpha].sub.i] be the volume (or weight) of the goods to be delivered to delivery customer i, [[beta].sub.i] the volume (or weight) of the goods to be picked up from collection customer i and Q the total capacity of the vehicle. Note that [[alpha].sub.i] = 0, [for all] i [member of] C, and [[beta].sub.i] = 0, [for all] [member of] D.
For the formulation, we use the edge variable [x.sub.ij], which is equal to...
|
