A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms

This paper introduces a pickup and delivery problem encountered in servicing of offshore oil and gas platforms in the Norwegian Sea. A single vessel must perform pickups and deliveries at several offshore platforms. All delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem, called the Single Vehicle Pickup and Delivery Problem with Capacitated Customers consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform), and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operations. This paper describes several construction heuristics as well as a tabu search algorithm. Computational results are presented.     

A column generation approach for location-routing problems with pickup and delivery

In this paper we formulate an integer programming model for the Location and Routing Problem with Pickup and Delivery. We propose a column generation scheme and implement, for the subproblem, a label-setting algorithm for the shortest path with pickup and delivery and time windows problem. We also propose a set of heuristics to speed up this process. To validate the model, we implement the column generation scheme and test it on different instances developed in this paper. We also provide an analysis of how the costs of opening depots and the fixed cost of routes affect the optimal solution.     

The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and several valid inequalities, some of which are facet defining, are introduced. Separation procedures and a branch-and-cut algorithm are developed. Computational results show that the algorithm is capable of solving to optimality instances involving up to 35 pickup and delivery requests, thus more than doubling the previous record of 15.      

Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery

This work proposes a Branch-cut-and-price (BCP) approach for the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We also deal with a particular case of the VRPSPD, known as the Vehicle Routing Problem with Mixed Pickup and Delivery. The BCP algorithm was tested in well-known benchmark instances involving up to 200 customers. Four instances were solved for the first time and some LBs were improved.     

Creating lasso-solutions for the traveling salesman problem with pickup and delivery by Tabu search

We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD) where the same costumers might require both deloverie of goods and pickup of other goods. All the goods should be transported from/to the same depot. A vehicle on a TSPPD-tour could often get some practical problems when arranging the load. Even if the vehicle has enough space for all the pickups, one has to consider that they are stored in a way that doesn't block the delivery for the next customer. In real life problems this occurs for instance for breweries when they deliver bottles of beer or mineral water and collects empty bottles from the same customers on the same tour. In these situations we could relax the constraints of only checking Hamiltonian tours, and also try solutions that can visit customers in a way giving rise to a ‘alsso’ model. A solution which first only delivers bottles until the vehicle is partly unloaded, then do both delivery and pickup at the remaining customers and at last picks up the empty bottle from the first visited customers, could in these situations be better than a pure Hamiltonian tour, at least in a practical setting. To find such solutions, we will use the metaheuristic Tabu Search on some well known TSPPD-problems, and compare them to other kinds of solutions on the same problems.     

Decision diagrams for solving traveling salesman problems with pickup and delivery in real time

The Traveling Salesman Problem with Pickup and Delivery seeks a minimum cost path with pickups preceding deliveries. It is important in on-demand last-mile logistics, such as ride sharing and meal delivery. We examine the use of low-width Decision Diagrams in a branch-and-bound with and without Assignment Problem inference duals as a primal heuristic for finding good solutions within strict time budgets. We show these diagrams can be more effective than similarly structured hybrid Constraint Programming techniques for real-time decision making.     

A unified heuristic for a large class of Vehicle Routing Problems with Backhauls

The Vehicle Routing Problem with Backhauls is a generalization of the ordinary capacitated vehicle routing problem where goods are delivered from the depot to the linehaul customers, and additional goods are brought back to the depot from the backhaul customers. Numerous ways of modeling the backhaul constraints have been proposed in the literature, each imposing different restrictions on the handling of backhaul customers. A survey of these models is presented, and a unified model is developed that is capable of handling most variants of the problem from the literature. The unified model can be seen as a Rich Pickup and Delivery Problem with Time Windows, which can be solved through an improved version of the large neighborhood search heuristic proposed by Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Technical Report, DIKU, University of Copenhagen, 2004]. The results obtained in this way are comparable to or improve on similar results found by state of the art heuristics for the various variants of the problem. The heuristic has been tested on 338 problems from the literature and it has improved the best known solution for 227 of these. An additional benefit of the unified modeling and solution method is that it allows the dispatcher to mix various variants of the Vehicle Routing Problem with Backhauls for the individual customers or vehicles.     

An empirical study on the benefit of split loads with the pickup and delivery problem

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip has been shown to have benefit for both the classic Vehicle Routing Problem (VRP) and the Pickup and Delivery Problem (PDP). However, the magnitude of the benefit may be affected by various problem characteristics. In this paper, we characterize those real world environments in which split loads are most likely to be beneficial. Based on practitioner interest, we determine how the benefit is affected by the mean load size and variance, number of origins relative to the number of destinations, the percentage of origin–destination pairs with a load requiring service, and the clustering of origin and destination locations. We find that the magnitude of benefit is greatest for load sizes just over one half vehicle capacity as these loads can not be combined without splitting, while they are the easiest to combine on a vehicle with splitting; increases as the number of loads sharing an origin or destination increases because there are more potential load combinations to split at each stop; and increases as the average distance from an origin to a destination increases because splitting loads reduces the trips from origins to destinations.     

有时间窗装卸问题的多策略分组编码遗传算法

根据有时间窗装卸问题(PDPTW)的数学模型,设计了多策略分组编码遗传算法,将禁忌思想用于产生可行解的启发式插入算法之中,对计算实例进行了求解,结果表明,此算法可以有效求得有时间窗装卸问题的近似最优解.     

Static pickup and delivery problems: a classification scheme and survey

Pickup and delivery problems constitute an important class of vehicle routing problems in which objects or people have to be collected and distributed. This paper introduces a general framework to model a large collection of pickup and delivery problems, as well as a three-field classification scheme for these problems. It surveys the methods used for solving them. This invited paper is discussed in the comments available at: , , , , .     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

Models and Algorithms for Carsharing Systems and Related Problems

In a Carsharing System, a fleet of cars is distributed at specified stations in an urban area, users can take and return cars at any time and station. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the total number of places and the number of cars in each station, in order to refuse as few customer requests as possible. In this work, we propose to model the resulting problem of balancing the load of the stations as a General Pickup and Delivery Problem. As problems of this type are known to be hard, we discuss possible heuristic approaches both for the static (offline) and the dynamic (online) version of the problem, and give approximation results for special cases.     

Simulation and optimisation of intermodal barge transport networks

This is a summary of the author??s PhD thesis supervised by Gerrit Janssens and Cathy Macharis and defended on 7 May 2010?at the Hasselt University, Belgium. The thesis is written in English and is available from the author upon request. This work deals with two key aspects in the competitiveness of intermodal transport making use of inland navigation. The first part of the thesis studies bundling of freight in intermodal barge transport networks. Alternative bundling strategies for container barge transport are compared by means of discrete event simulation. Cooperation between inland barge terminals to bundle freight flows is modelled as a service network design problem. The second part relates to the initial and final journey by road in the intermodal barge transport chain. Pre- and end-haulage by road is modelled as a Full Truckload Pickup and Delivery Problem with Time Windows. A local search algorithm and deterministic annealing algorithm are proposed to find near-optimal solutions.     

The static bicycle relocation problem with demand intervals

This study introduces the Static Bicycle Relocation Problem with Demand Intervals (SBRP-DI), a variant of the One Commodity Pickup and Delivery Traveling Salesman Problem (1-PDTSP). In the SBRP-DI, the stations are required to have an inventory of bicycles lying between given lower and upper bounds and initially have an inventory which does not necessarily lie between these bounds. The problem consists of redistributing the bicycles among the stations, using a single capacitated vehicle, so that the bounding constraints are satisfied and the repositioning cost is minimized. The real-world application of this problem arises in rebalancing operations for shared bicycle systems. The repositioning subproblem associated with a fixed route is shown to be a minimum cost network problem, even in the presence of handling costs. An integer programming formulation for the SBRP-DI are presented, together with valid inequalities adapted from constraints derived in the context of other routing problems and a Benders decomposition scheme. Computational results for instances adapted from the 1-PDTSP are provided for two branch-and-cut algorithms, the first one for the full formulation, and the second one with the Benders decomposition.     

Data mining-based dispatching system for solving the local pickup and delivery problem

The Local Pickup and Delivery Problem (LPDP) has drawn much attention, and optimization models and algorithms have been developed to address this problem. However, for real world applications, the large-scale and dynamic nature of the problem causes difficulties in getting good solutions within acceptable time through standard optimization approaches. Meanwhile, actual dispatching solutions made by field experts in transportation companies contain embedded dispatching rules. This paper introduces a Data Mining-based Dispatching System (DMDS) to first learn dispatching rules from historical data and then generate dispatch solutions, which are shown to be as good as those generated by expert dispatchers in the intermodal freight industry. Three additional benefits of DMDS are: (1) it provides a simulation platform for strategic decision making and analysis; (2) the learned dispatching rules are valuable to combine with an optimization algorithm to improve the solution quality for LPDPs; (3) by adding optimized solutions to the training data, DMDS is capable to generate better-than-actuals solutions very quickly.     

Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban

In this paper, we extend the classical Pickup and Delivery Problem (PDP) to an integrated routing and three-dimensional loading problem, called PDP with three-dimensional loading constraints (3L-PDP). We are given a set of requests and a homogeneous fleet of vehicles. A set of routes of minimum total length has to be determined such that each request is transported from a loading site to the corresponding unloading site. In the 3L-PDP, each request is given as set of rectangular boxes and the vehicle capacity is replaced by a 3D loading space.This paper is the second one in a series of articles on 3L-PDP. As in the first paper we are dealing with constraints which guarantee that no reloading effort will occur. Here the focus is laid on the reloading ban, a packing constraint that ensures identical placements of same boxes in different packing plans. The reloading ban allows for better solutions in terms of travel distance than a routing constraint that was used in the first paper to preclude any reloading effort. To implement this packing constraint a new type of packing procedure is needed that is capable to generate a series of interrelated packing plans per route. This packing procedure, designed as tree search algorithm, and the corresponding concept of packing checks is the main contribution of the paper at hand. The packing procedure and a large neighborhood search procedure for routing form a hybrid algorithm for the 3L-PDP. Computational experiments were performed using 54 3L-PDP benchmark instances.     

A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.     

A note on branch-and-cut-and-price

In this paper, we propose a methodology for branch-and-cut-and-price when cuts and columns are generated simultaneously. The methodology is illustrated with two application cases: the Split Delivery Vehicle Routing Problem (SDVRP) and the Bus Rapid Transit Route Design Problem (BRTRDP).     

Lasso solution strategies for the vehicle routing problem with pickups and deliveries

This paper considers the vehicle routing problem with pickups and deliveries (VRPPD) where the same customer may require both a delivery and a pickup. This is the case, for instance, of breweries that deliver beer or mineral water bottles to a set of customers and collect empty bottles from the same customers. It is possible to relax the customary practice of performing a pickup when delivering at a customer, and postpone the pickup until the vehicle has sufficient free capacity. In the case of breweries, these solutions will often consist of routes in which bottles are first delivered until the vehicle is partly unloaded, then both pickup and delivery are performed at the remaining customers, and finally empty bottles are picked up from the first visited customers. These customers are revisited in reverse order, thus giving rise to lasso shaped solutions. Another possibility is to relax the traditional problem even more and allow customers to be visited twice either in two different routes or at different times on the same route, giving rise to a general solution. This article develops a tabu search algorithm capable of producing lasso solutions. A general solution can be reached by first duplicating each customer and generating a Hamiltonian solution on the extended set of customers. Test results show that while general solutions outperform other solution shapes in term of cost, their computation can be time consuming. The best lasso solution generated within a given time limit is generally better than the best general solution produced with the same computing effort.     

Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design

Maritime cabotage is a legislation published by a particular coastal country, which is used to conduct the cargo transportation between its two domestic ports. This paper proposes a two-phase mathematical programming model to formulate the liner hub-and-spoke shipping network design problem subject to the maritime cabotage legislations, i.e., the hub location and feeder allocation problem for phase I and the ship route design with ship fleet deployment problem for phase II. The problem in phase I is formulated as a mixed-integer linear programming model. By developing a hub port expanding technique, the problem in phase II is formulated as a vehicle routing problem with pickup and delivery. A Lagrangian relaxation based solution method is proposed to solve it. Numerical implementations based on the Asia–Europe–Oceania shipping services are carried out to account for the impact analysis of the maritime cabotage legislations on liner hub-and-spoke shipping network design problem.