A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling

We investigate an extension to the classical insertion-based heuristic for the vehicle routing problem with backhauling (VRPB). It is based on the idea of inserting more than one backhaul at a time. This method is tested on data sets with single and multiple depots with encouraging results at no additional computational burden. This approach can also be useful in generating good starting solutions for the more computer-intensive meta-heuristics.     

Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls

Recently, an increasing number of papers on vehicle routing problems with backhauling has been published. Different types of backhauling problems are discussed. Two of them—the vehicle routing problem with backhauls and so-called ‘mixed loads’ (VRPBM) and the vehicle routing problem with simultaneous delivery and pick-up (VRPSDP)—are closely related. In this paper, we discuss that relationship. Our findings are that previously published results for VRPSDP instances obtained by using a heuristic suggested for the VRPBM do not take into account specific properties of the VRPSDP. As a result of the analysis of the relation between both problem types the possibility of solving the VRPBM by applying an insertion heuristic based on the concept of ‘residual capacities’ originally designed for the VRPSDP is investigated. Numerical results indicate that, for certain instances, this approach is more favourable than the application of a heuristic suggested for the VRPBM in the literature.     

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model

In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo-polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time.     

Heuristics for vehicle routing on tree-like networks

This paper presents two new heuristics for the vehicle routing problem on tree-like road networks. These networks occur, for example, in rural road systems where the supply (or delivery) nodes are located on rural roads leading off from a few highways which form the ‘trunks’ of a tree-like network. The heuristics have the conventional objective of minimising the total distance travelled by the vehicles. The development of the heuristics takes advantage of the tree-like structure of the network. These two new heuristics and two other heuristics from the published literature are applied to some test problems and computational results are presented. The computational experience indicates that one of the new heuristics provides superior solutions to the existing heuristics and in reasonable computing time. It therefore appears suitable for large-scale practical routing problems.     

A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.     

Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data

We address an integrated logistic system where decisions on location of depot, vehicle routing and assignment of routes to vehicles are considered simultaneously. Total cost and workload balance are common criteria influencing decision-making. Literature on location-routing problems addressed the location and vehicle routing decisions with a common assumption of assigning one route to one vehicle. However, the cost of acquiring vehicles (and crew) is often more significant than the routing cost. This notion of assigning several routes to a vehicle during the routing procedure is explored in our integrated model. We apply metaheuristics of tabu search and simulated annealing on real data and simulated data, to compare their performances under two versions: simultaneous or sequential routes assignment to vehicles. A new statistical procedure is proposed to compare two algorithms on the strength of their multi-objective solutions. Results show that the simultaneous versions have advantage over the sequential versions in problems where routes are capacity-constrained, but not in the time dimension. The simultaneous versions are also more effective in generating non-dominated solutions than the sequential versions.     

Column generation for vehicle routing problems with multiple synchronization constraints

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.     

Heuristic solution approaches for the cumulative capacitated vehicle routing problem

Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.     

Large scale stochastic inventory routing problems with?split delivery and service level constraints

A stochastic inventory routing problem (SIRP) is typically the combination of stochastic inventory control problems and NP-hard vehicle routing problems, which determines delivery volumes to the customers that the depot serves in each period, and vehicle routes to deliver the volumes. This paper aims to solve a large scale multi-period SIRP with split delivery (SIRPSD) where a customer??s delivery in each period can be split and satisfied by multiple vehicle routes if necessary. This paper considers SIRPSD under the multi-criteria of the total inventory and transportation costs, and the service levels of customers. The total inventory and transportation cost is considered as the objective of the problem to minimize, while the service levels of the warehouses and the customers are satisfied by some imposed constraints and can be adjusted according to practical requests. In order to tackle the SIRPSD with notorious computational complexity, we first propose an approximate model, which significantly reduces the number of decision variables compared to its corresponding exact model. We then develop a hybrid approach that combines the linearization of nonlinear constraints, the decomposition of the model into sub-models with Lagrangian relaxation, and a partial linearization approach for a sub model. A near optimal solution of the model found by the approach is used to construct a near optimal solution of the SIRPSD. Randomly generated instances of the problem with up to 200 customers and 5 periods and about 400 thousands decision variables where half of them are integer are examined by numerical experiments. Our approach can obtain high quality near optimal solutions within a reasonable amount of computation time on an ordinary PC.     

The vehicle routing problem with flexible time windows and traveling times

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.