New neighborhood structures for the Double Traveling Salesman Problem with Multiple Stacks

The changing requirements in transportation and logistics have recently induced the appearance of new vehicle routing problems that include complex constraints as precedence or loading constraints. One of these problems that have appeared during the last few years is the Double Traveling Salesman Problem with Multiple Stacks (DTSPMS), a vehicle routing problem in which some pickups and deliveries must be performed in two independent networks, verifying some precedence and loading constraints imposed on the vehicle. In this paper, four new neighborhood structures for the DTSPMS based on reinsertion and permutation of orders to modify both the routes and the loading planning of the solutions are introduced and described in detail. They can be used in combination with any metaheuristic using local search as a subprocedure, guiding the search to unexplored zones of the solution space. Some computational results obtained using all proposed neighborhood structures are presented, providing good quality solutions for real sized instances.      

Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints

Logistics and transportation issues have been receiving increasing attention during the last decades and their requirements have gradually changed, making it necessary to take into account new situations and conditions. The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) is a pickup and delivery problem in which some additional precedence and loading constraints are imposed on the vehicle to be used. In this paper we approach the problem using intermediate infeasible solutions to diversify the search process and we develop some fixing procedures and infeasibility measures to deal with this kind of solutions and take advantage of their potential.     

Notes on the single route lateral transhipment problem

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.     

Vehicle routing problem with simultaneous deliveries and pickups

The vehicle routing problem with backhauls involves the delivery and pickup of goods at different customer locations. In many practical situations, however, the same customer may require both a delivery of goods from the distribution centre and a pickup of recycled items simultaneously. In this paper, an insertion-based procedure to generate good initial solutions and a heuristic based on the record-to-record travel, tabu lists, and route improvement procedures are proposed to resolve the vehicle routing problems with simultaneous deliveries and pickups. Computational characteristics of the insertion-based procedure and the hybrid heuristic are evaluated through computational experiments. Computational results show that the insertion-based procedure obtained better solutions than those found in the literature. Computational experiments also show that the proposed hybrid heuristic is able to reduce the gap between initial solutions and optimal solutions effectively and is capable of obtaining optimal solutions very efficiently for small-sized problems.     

一类新的车辆路径问题及其两阶段算法

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法：两阶段算法. 最后在改进的Solomn的算例的基础上,进行了数值试验.     

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.     

A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services

This study investigates a multi-visit flexible-docking vehicle routing problem that uses a truck and drone fleet to fulfill pickup and delivery requests in rural areas. In this collaborative truck–drone system, each drone may serve multiple customers per trip (multi-visit services), dock to the same or different truck from where it launched (flexible docking), and perform simultaneous pickup and delivery. These characteristics complicate the temporal, spatial, and loading synchronization for trucks and drones, making the decisions of order allocation and vehicle routing highly interdependent and intractable. This problem is formulated as a mixed-integer linear programming model and solved by a tailored adaptive large neighborhood search metaheuristic. Numerical experiments are conducted on sparse rural networks to demonstrate the efficiency of the proposed method. We observe that the proposed truck–drone system shows an average cost saving of 34% compared to the truck-only case. Moreover, deep insights into the impacts of multi-visit services, flexible docking, and simultaneous pickup and delivery on the performance of the truck–drone system are discussed.     

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 General Vehicle Routing Problem

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.     

General solutions to the single vehicle routing problem with pickups and deliveries

The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice.     

Two-echelon vehicle routing problem with satellite bi-synchronization

In considering route optimization at a series of express stages from pickup to delivery via the intercity linehaul, we introduce the two-echelon vehicle routing problem with satellite bi-synchronization (2E-VRP-SBS) from the perspective of modeling the routing problems of two-echelon networks. The 2E-VRP-SBS involves the inter-satellite linehaul on the first echelon, and the pickups from senders to origin satellites (i.e., satellites for cargo collection) and deliveries from destination satellites (i.e., satellites for cargo deliveries) to receivers on the second echelon. The 2E-VRP-SBS integrates satellite bi-synchronization constraints, multiple vehicles, and time window constraints on the two-echelon network and aims to find cost-minimizing routes for various types of trucks. Satellite bi-synchronization constraints, which synchronously guarantee the synchronization at origin satellites and the synchronization at destination satellites, provide an innovative method to formulate the two-echelon routing problem. In this study, we develop a mixed-integer programming model for the 2E-VRP-SBS. An exact method using CPLEX solver is presented and a modified adaptive large neighborhood search is conducted. Furthermore, the effectiveness of the 2E-VRP-SBS formulation and the applicability of the heuristic for various instances are experimentally evaluated.     

Integer linear programming models for a cement delivery problem

We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints. We first propose a two phase solution method that assigns deliveries to the vehicles, and then builds vehicle routes. Both subproblems are formulated as integer linear programming problems. We then show how to combine the two phases in a single integer linear program. Experiments on real life instances are performed to compare the performance of the two solution methods.     

带时间窗分车运输同时收发车辆路径问题及其启发式算法

本文结合汽车零部件第三方物流的实际背景,提出了带时间窗的可分车运输同时收发车辆路径问题(简称SVRPSPDTW),并给出了问题的数学模型,同时提出两个求解该问题的启发式算法,最后进行了数值试验.由于没有可以利用的算例,本文在Solomn测试基准库的基础上构建了针对新问题的算例.计算结果表明,所有算例计算时间均不超过1秒,且算法1无论是从车辆的使用数还是从车辆行驶的路径总长度上都明显优于算法2,从而说明算法1是寻找SVRPSPDTW问题初始可行解的较为有效的算法.     

The tree representation for the pickup and delivery traveling salesman problem with LIFO loading

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are commonly represented by vertex lists. However, when the TSPPD is required to follow a policy that loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a novel variable neighborhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Extensive experiments suggest that our VNS heuristic is superior to the current best heuristics for the TSPPDL in terms of solution quality, while requiring no more computing time as the size of the problem increases.     

An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls

In this article, a visual interactive approach based on a new greedy randomised adaptive memory programming search (GRAMPS) algorithm is proposed to solve the heterogeneous fixed fleet vehicle routing problem (HFFVRP) and a new extension of the HFFVRP, which is called heterogeneous fixed fleet vehicle routing problem with backhauls (HFFVRPB). This problem involves two different sets of customers. Backhaul customers are pickup points and linehaul customers are delivery points that are to be serviced from a single depot by a heterogeneous fixed fleet of vehicles, each of which is restricted in the capacity it can carry, with different variable travelling costs.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care

This paper addresses a vehicle scheduling problem encountered in home health care logistics. It concerns the delivery of drugs and medical devices from the home care company’s pharmacy to patients’ homes, delivery of special drugs from a hospital to patients, pickup of bio samples and unused drugs and medical devices from patients. The problem can be considered as a special vehicle routing problem with simultaneous delivery and pickup and time windows, with four types of demands: delivery from depot to patient, delivery from a hospital to patient, pickup from a patient to depot and pickup from a patient to a medical lab. Each patient is visited by one vehicle and each vehicle visits each node at most once. Patients are associated with time windows and vehicles with capacity. Two mixed-integer programming models are proposed. We then propose a Genetic Algorithm (GA) and a Tabu Search (TS) method. The GA is based on a permutation chromosome, a split procedure and local search. The TS is based on route assignment attributes of patients, an augmented cost function, route re-optimization, and attribute-based aspiration levels. These approaches are tested on test instances derived from existing VRPTW benchmarks.     

不确定同时取送货车辆路径问题及粒子群算法研究

研究了不确定同时取送货车辆路径问题(VRPSPD),考虑运行环境的不确定性,顾客时间窗口要求和对顾客同时进行取货和送货服务的情况,以运作成本最低和顾客满意度最高为决策目标,构建不确定VRPSPD数学模型。模型中,引入模糊随机理论来描述决策环境中的双重不确定性,假定顾客需求量(送货量)和取货量是模糊随机变量。随后,提出基于模糊随机算子的改进粒子群算法对模型进行求解。为了适应模型特点和提高算法效率,设计合理的编码和解码过程,制定多个适应度函数方案处理多目标问题,并应用更加科学的更新策略。最后在应用案例中,通过参数测试获取合理的算法参数取值,采用计算结果分析和求解算法测评验证模型和算法的有效性。     

An optimization approach for planning daily drayage operations

Daily drayage operations involve moving loaded or empty equipment between customer locations and rail ramps. Our goal is to minimize the cost of daily drayage operations in a region on a given day. Drayage orders are generally pickup and delivery requests with time windows. The repositioning of empty equipment may also be required in order to facilitate loaded movements. The drayage orders are satisfied by a heterogeneous fleet of drivers. Driver routes must satisfy various operational constraints. We present an optimization methodology for finding cost-effective schedules for regional daily drayage operations. The core of the formulation is a set partitioning model whose columns represent routes. Routes are added to the formulation by column generation. We present numerical results for real-world data which demonstrate that our methodology produces low cost solutions in a reasonably short time.     

A tabu search algorithm for the multi-trip vehicle routing and scheduling problem

This paper describes a novel tabu search heuristic for the multi-trip vehicle routing and scheduling problem (MTVRSP). The method was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice. In the MTVRSP, besides the constraints that are common to the basic vehicle routing problem, the following ones are present: during each day a vehicle can make more than one trip; the customers impose delivery time windows; the vehicles have different capacities considered in terms of both volume and weight; the access to some customers is restricted to some vehicles; the drivers' schedules must respect the maximum legal driving time per day and the legal time breaks; the unloading times are considered.