A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

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.     

Metaheuristics with disposal facility positioning for the waste collection VRP with time windows

This paper improves heuristic algorithms presented in Benjamin and Beasley (Comput Oper Res 37(12):2270–2280, 2010) for solving the waste collection vehicle routing problem with time windows, particularly the real life waste collection benchmark problems from Kim et al. (Comput Oper Res 33(12):3624–3642, 2006). These consist of ten test problems, involving up to 2,092 customers and 19 waste disposal facilities. The main difference between this paper and Benjamin and Beasley (Comput Oper Res 37(12):2270–2280, 2010) is that here we use a disposal facility positioning (DFP) procedure to evaluate routes for our algorithms. Since the problem involves multiple disposal facilities, the objective of DFP is to choose the best disposal facilities to go on the vehicle route. Computational results indicate that our algorithms with DFP produce substantially better quality routes than previous approaches in the literature.     

An integrated approach for collection network design,capacity planning and vehicle routing in reverse logistics

This study considers network design, capacity planning and vehicle routing for collection systems in reverse logistics. The network design and capacity planning problems are to determine the static locations and capacities of collection points as well as the dynamic allocations of demand points to the opened collection points over a planning horizon, and the vehicle routing problem is to determine the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot while satisfying the return demands at collection points and the vehicle capacity. The objective is to minimize the sum of fixed costs to open collection points and to acquire vehicles as well as variable costs to transport returns at demand points to the opened collection points and travel the opened collection points by vehicles. Unlike the location-routing problems, the integrated problem considered in this study has several features: multi-period dynamic model, capacity planning for collection points, maximum allowable collection distances, etc. To solve the integrated problem, two types of tabu search algorithms, hierarchical and integrated ones, are suggested, and their test results are reported. In particular, the efficiency of the integrated approach is shown by comparing the two algorithm types.     

The rollon–rolloff waste collection vehicle routing problem with time windows

This study introduces a rollon–rolloff waste collection vehicle routing problem involving large containers that accumulate huge amounts of garbage at construction sites and shopping districts. In this problem, tractors move one container at a time between customer locations, a depot, disposal facilities, and container storage yards. The complicated constraints discussed in this study arise from having multiple disposal facilities, multiple container storage yards, seven service types of customer demands, different time windows for customer demands and facilities, various types and sizes of containers, and the lunch break of tractor drivers. In addition, real-world issues, such as changing service types, multiple demands at a customer’s location, and tractors with different work schedules, are dealt with. This study proposes a large neighborhood search based iterative heuristic approach consisting of several algorithms for the problem. The effectiveness of the proposed methods is demonstrated by computational experiments using benchmark data, some instances of which are derived from real-world problems.     

Heuristic solutions for the vehicle routing problem with time windows and synchronized visits

We present a simulated annealing based algorithm for a variant of the vehicle routing problem (VRP), in which a time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. The problem is called the VRP with time windows and synchronized visits. The algorithm features a set of local improvement methods to deal with various objectives of the problem. Experiments conducted on the benchmark instances from the literature clearly show that our method is fast and outperforms the existing approaches. It produces all known optimal solutions of the benchmark in very short computational times, and improves the best results for the rest of the instances.     

Local search-based metaheuristics for the split delivery vehicle routing problem

The split delivery vehicle routing problem is a variant of the standard vehiclerouting problem where the single-visit assumption is waived and a customer mightbe served on more than one vehicle tour. In this article we report on a studywhere we have applied the standard local search-based metaheuristics usingadaptations of the most widely used inter-tour and intra-tour exchange operatorsfor solving the standard vehicle routing problem now allowing splitting andjoining of deliveries. As we will show we could find new best solutions for 51out of 57 benchmark instances, which have been defined for this problemclass.     

A memetic algorithm for the multiperiod vehicle routing problem with profit

In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

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

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

Designing routes for WEEE collection: the vehicle routing problem with split loads and date windows

This paper presents an integer programming model and describes a GRASP based algorithm to solve a vehicle routing and scheduling problem for the collection of Waste of Electric and Electronic Equipment (WEEE). The difficulty of this problem arises from the fact that it is characterized by four variants of the vehicle routing problem that have been studied independently in the literature, but not together. The experimental analysis on a large set of randomly-generated instances shows the good performance of the proposed algorithm. Moreover, computational results using real data show that the method outperforms real existing approaches to reverse logistics.     

A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries

The asymmetric vehicle routing problem with simultaneous pickup and deliveries is considered. This paper develops four new classes of valid inequalities for the problem. We generalize the idea of a no-good cut. Together, these help us solve 45-node randomly generated problem instances more efficiently. We report results on a set of benchmark instances in literature. In this set, we are able to show an order of magnitude improvement in computational times over currently published results in literature.     

Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm

In this paper, the dynamic capacitated location-routing problem with fuzzy demands (DCLRP-FD) is considered. In the DCLRP-FD, facility location problem and vehicle routing problem are solved on a time horizon. Decisions concerning facility locations are permitted to be made only in the first time period of the planning horizon but, the routing decisions may be changed in each time period. Furthermore, the vehicles and depots have a predefined capacity to serve the customers with altering demands during the time horizon. It is assumed that the demands of customers are fuzzy variables. To model the DCLRP-FD, a fuzzy chance-constrained programming is designed based upon the fuzzy credibility theory. To solve this problem, a hybrid heuristic algorithm (HHA) with four phases including the stochastic simulation and a local search method are proposed. To achieve the best value of two parameters of the model, the dispatcher preference index (DPI) and the assignment preference index (API), and to analyze their influences on the final solution, numerical experiments are carried out. Moreover, the efficiency of the HHA is demonstrated via comparing with the lower bound of solutions and by using a standard benchmark set of test problems. The numerical examples show that the proposed algorithm is robust and could be used in real world problems.     

A unified tabu search heuristic for vehicle routing problems with time windows

This paper presents a unified tabu search heuristic for the vehicle routing problem with time windows and for two important generalizations: the periodic and the multi-depot vehicle routing problems with time windows. The major benefits of the approach are its speed, simplicity and flexibility. The performance of the heuristic is assessed by comparing it to alternative methods on benchmark instances of the vehicle routing problem with time windows. Computational experiments are also reported on new randomly generated instances for each of the two generalizations.     

A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints

The two-dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP) is a variant of the classical vehicle routing problem in which customers are served by a heterogeneous fleet of vehicles. These vehicles have different capacities, fixed and variable operating costs, length and width in dimension, and two-dimensional loading constraints. The objective of this problem is to minimize transportation cost of designed routes, according to which vehicles are used, to satisfy the customer demand. In this study, we proposed a simulated annealing with heuristic local search (SA_HLS) to solve the problem and the search was then extended with a collection of packing heuristics to solve the loading constraints in 2L-HFVRP. To speed up the search process, a data structure was used to record the information related to loading feasibility. The effectiveness of SA_HLS was tested on benchmark instances derived from the two-dimensional loading vehicle routing problem (2L-CVRP). In addition, the performance of SA_HLS was also compared with three other 2L-CVRP models and four HFVRP methods found in the literature.     

A post-improvement procedure for the mixed load school bus routing problem

This paper aims to develop a mixed load algorithm for the school bus routing problem (SBRP) and measure its effects on the number of required vehicles. SBRP seeks to find optimal routes for a fleet of vehicles, where each vehicle transports students from their homes and to their schools while satisfying various constraints. When mixed load is allowed, students of different schools can get on the same bus at the same time. Although many of real world SBRP allow mixed load, only a few studies have considered these cases. In this paper, we present a new mixed load improvement algorithm and compare it with the only existing algorithm from the literature. Benchmark problems are proposed to compare the performances of algorithms and to stimulate other researchers’ further study. The proposed algorithm outperforms the existing algorithm on the benchmark problem instances. It has also been successfully applied to some of real-world SBRP and could reduce the required number of vehicles compared with the current practice.     

A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes

Multi-compartment vehicle routing problems arise in a variety of problem settings in which different product types have to be transported separated from each other. In this paper, a problem variant which occurs in the context of glass waste recycling is considered. In this problem, a set of locations exists, each of which offering a number of containers for the collection of different types of glass waste (e.g. colorless, green, brown glass). In order to pick up the contents from the containers, a fleet of homogeneous disposal vehicles is available. Individually for each disposal vehicle, the capacity can be discretely separated into a limited number of compartments to which different glass waste types are assigned. The objective of the problem is to minimize the total distance to be travelled by the disposal vehicles. For solving this problem to optimality, a branch-and-cut algorithm has been developed and implemented. Extensive numerical experiments have been conducted in order to evaluate the algorithm and to gain insights into the problem structure. The corresponding results show that the algorithm is able to solve instances with up to 50 locations to optimality and that it reduces the computing time by 87% compared to instances from the literature. Additional experiments give managerial insights into the use of different variants of compartments with flexible sizes.

     

Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows

This note introduces a refinement to a previously proposed tabu search algorithm for vehicle routing problems with time windows. This refinement yields new best known solutions on a set of benchmark instances of the multi-depot, the periodic and the site-dependent vehicle routing problems with time windows.     

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.      

A customer-centric routing problem with multiple trips of a single vehicle

In this study, we introduce a routing problem with multiple uses of a single vehicle and service time in demand points, minimizing the sum of clients’ waiting time to receive service. This problem is relevant in the distribution of aid in disaster-stricken communities, in the recollection and/or delivery of perishable goods and personnel transportation, among other situations, where reaching clients to perform service, fast and fair, is a priority. We consider vehicle capacity and travel distance constraints, forcing multiple use of the vehicle during the planning horizon. This paper presents two mixed integer formulations for this problem, based on a multi-level network, as well as a metaheuristic algorithm. The proposed models can solve to optimality instances with up to 30 clients. The proposed metaheuristic algorithm obtains high-quality solutions in short computational times.