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.     

A heuristic solution method for node routing based solid waste collection problems

This paper considers a real world waste collection problem in which glass, metal, plastics, or paper is brought to certain waste collection points by the citizens of a certain region. The collection of this waste from the collection points is therefore a node routing problem. The waste is delivered to special sites, so called intermediate facilities (IF), that are typically not identical with the vehicle depot. Since most waste collection points need not be visited every day, a planning period of several days has to be considered. In this context three related planning problems are considered. First, the periodic vehicle routing problem with intermediate facilities (PVRP-IF) is considered and an exact problem formulation is proposed. A set of benchmark instances is developed and an efficient hybrid solution method based on variable neighborhood search and dynamic programming is presented. Second, in a real world application the PVRP-IF is modified by permitting the return of partly loaded vehicles to the depots and by considering capacity limits at the IF. An average improvement of 25% in the routing cost is obtained compared to the current solution. Finally, a different but related problem, the so called multi-depot vehicle routing problem with inter-depot routes (MDVRPI) is considered. In this problem class just a single day is considered and the depots can act as an intermediate facility only at the end of a tour. For this problem several instances and benchmark solutions are available. It is shown that the algorithm outperforms all previously published metaheuristics for this problem class and finds the best solutions for all available benchmark instances.     

The distance constrained multiple vehicle traveling purchaser problem

In the Distance Constrained Multiple Vehicle Traveling Purchaser Problem (DC-MVTPP) a fleet of vehicles is available to visit suppliers offering products at different prices and with different quantity availabilities. The DC-MVTPP consists in selecting a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while ensuring that the distance traveled by each vehicle does not exceed a predefined upper bound. The problem generalizes the classical Traveling Purchaser Problem (TPP) and adds new realistic features to the decision problem. In this paper we present different mathematical programming formulations for the problem. A branch-and-price algorithm is also proposed to solve a set partitioning formulation where columns represent feasible routes for the vehicles. At each node of the branch-and-bound tree, the linear relaxation of the set partitioning formulation, augmented by the branching constraints, is solved through column generation. The pricing problem is solved using dynamic programming. A set of instances has been derived from benchmark instances for the asymmetric TPP. Instances with up to 100 suppliers and 200 products have been solved to optimality.     

The application of a vehicle routing model to a waste-collection problem: two case studies

In this paper we suggest a unique model for estimating the operating cost of each of three waste-collection systems. Under the traditional system, which is widely used, waste is typically collected in plastic bags and a three-man crew is needed on each vehicle. The other two systems require a one-man crew for vehicle collecting street containers. The side-loader system with fixed body automatically empties street containers into the vehicle body and empties the load at the disposal site. The side-loader system with demountable body allows the separation of the waste collection phase from transport to the disposal site, since the vehicle body can be demounted. We also present two case studies and show how the estimation of operating costs is a critical issue in decisions regarding the type of system to be used for waste collection.     

A path relinking algorithm for a multi-depot periodic vehicle routing problem

In this paper, we consider a multi-depot periodic vehicle routing problem which is characterized by the presence of a homogeneous fleet of vehicles, multiple depots, multiple periods, and two types of constraints that are often found in reality, i.e., vehicle capacity and route duration constraints. The objective is to minimize total travel costs. To tackle the problem, we propose an efficient path relinking algorithm whose exploration and exploitation strategies enable the algorithm to address the problem in two different settings: (1) As a stand-alone algorithm, and (2) As a part of a co-operative search algorithm called integrative co-operative search. The performance of the proposed path relinking algorithm is evaluated, in each of the above ways, based on standard benchmark instances. The computational results show that the developed PRA performs well, in both solution quality and computational efficiency.     

A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows

This paper presents a novel three-phase heuristic/algorithmic approach for the multi-depot routing problem with time windows and heterogeneous vehicles. It has been derived from embedding a heuristic-based clustering algorithm within a VRPTW optimization framework. To this purpose, a rigorous MILP mathematical model for the VRPTW problem is first introduced. Likewise other optimization approaches, the new formulation can efficiently solve case studies involving at most 25 nodes to optimality. To overcome this limitation, a preprocessing stage clustering nodes together is initially performed to yield a more compact cluster-based MILP problem formulation. In this way, a hierarchical hybrid procedure involving one heuristic and two algorithmic phases was developed. Phase I aims to identifying a set of cost-effective feasible clusters while Phase II assigns clusters to vehicles and sequences them on each tour by using the cluster-based MILP formulation. Ordering nodes within clusters and scheduling vehicle arrival times at customer locations for each tour through solving a small MILP model is finally performed at Phase III. Numerous benchmark problems featuring different sizes, clustered/random customer locations and time window distributions have been solved at acceptable CPU times.     

An efficient mixed integer programming model for pairing containers in inland transportation based on the assignment of orders

The inland transportation takes a significant portion of the total cost that arises from intermodal transportation. In addition, there are many parties (shipping lines, haulage companies, customers) who share this operation as well as many restrictions that increase the complexity of this problem and make it NP-hard. Therefore, it is important to create an efficient strategy to manage this process in a way to ensure all parties are satisfied. This paper investigates the pairing of containers/orders in drayage transportation from the perspective of delivering paired containers on 40-ft truck and/or individual containers on 20-ft truck, between a single port and a list of customer locations. An assignment mixed integer linear programming model is formulated, which solves the problem of how to combine orders in delivery to save the total transportation cost when orders with both single and multiple destinations exist. In opposition to the traditional models relying on the vehicle routing problem with simultaneous pickups and deliveries and time windows formulation, this model falls into the assignment problem category which is more efficient to solve on large size instances. Another merit for the proposed model is that it can be implemented on different variants of the container drayage problem: import only, import–inland and import–inland–export. Results show that in all cases the pairing of containers yields less cost compared to the individual delivery and decreases empty tours. The proposed model can be solved to optimality efficiently (within half hour) for over 300 orders.     

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.     

A bi-objective modeling approach applied to an urban semi-desirable facility location problem

This paper introduces a mixed-integer, bi-objective programming approach to identify the locations and capacities of semi-desirable (or semi-obnoxious) facilities. The first objective minimizes the total investment cost; the second one minimizes the dissatisfaction by incorporating together in the same function “pull” and “push” characteristics of the decision problem (individuals do not want to live too close, but they do not want to be too far, from facilities). The model determines the number of facilities to be opened, the respective capacities, their locations, their respective shares of the total demand, and the population that is assigned to each candidate site opened. The proposed approach was tested with a case study for a particular urban planning problem: the location of sorted waste containers. The complete set of (supported or unsupported) non-inferior solutions, consisting of combinations of multi-compartment containers for the disposal of four types of sorted waste in nineteen candidate sites, and population assignments, was generated. The results obtained for part of the historical center of an old European city (Coimbra, Portugal) show that this approach can be applied to a real-world planning scenario.     

Selective and periodic inventory routing problem for waste vegetable oil collection

We consider a biodiesel production company that collects waste vegetable oil from source points that generate waste in large amounts. The company uses the collected waste as raw material for biodiesel production. The manager of this company needs to decide which of the present source points to include in the collection program, which of them to visit on each day, which periodic routing schedule to repeat over an infinite horizon and how many vehicles to operate such that the total collection, inventory and purchasing costs are minimized while the production requirements and operational constraints are met. For this selective and periodic inventory routing problem, we propose two different formulations, compare them and apply the better performing one on a real-world problem with 36 scenarios. We generate lower bounds using a partial linear relaxation model, and observe that the solutions obtained through our model are within 3.28% of optimality on the average. Several insights regarding the customer selection, routing and purchasing decisions are acquired with sensitivity analysis.     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

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.     

Adapting the ng-path relaxation for bike balancing problems

This paper deals with a static bike relocation problem that deploys a fleet of vehicles to redistribute shared bicycles. To solve the problem to optimality, we present a branch-price-and-cut algorithm. In particular, a new path relaxation for the pricing problem is introduced that relaxes the constraints on the maximum number of bikes to move at each station in a similar fashion as elementary can be relaxed in vehicle routing problems. Computational results show that our algorithm outperforms the former state-of-the-art.     

A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery

This paper addresses a location-routing problem with simultaneous pickup and delivery (LRPSPD) which is a general case of the location-routing problem. The LRPSPD is defined as finding locations of the depots and designing vehicle routes in such a way that pickup and delivery demands of each customer must be performed with same vehicle and the overall cost is minimized. We propose an effective branch-and-cut algorithm for solving the LRPSPD. The proposed algorithm implements several valid inequalities adapted from the literature for the problem and a local search based on simulated annealing algorithm to obtain upper bounds. Computational results, for a large number of instances derived from the literature, show that some instances with up to 88 customers and 8 potential depots can be solved in a reasonable computation time.     

A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem

Surveillance applications require a collection of heterogeneous vehicles to visit a set of targets. We consider a fundamental routing problem that arises in these applications involving two vehicles. Specifically, we consider a routing problem where there are two heterogeneous vehicles that start from distinct initial locations and a set of targets. The objective is to find a tour for each vehicle such that each of the targets is visited at least once by a vehicle and the sum of the distances traveled by the vehicles is minimal. We consider an important special case of this routing problem where the travel costs satisfy the triangle inequality and the following monotonicity property: the first vehicle’s cost of traveling between any two targets is at most equal to the second vehicle’s cost of traveling between the same targets. We present a primal-dual algorithm for this case that provides an approximation ratio of 2.     

开放式多中心需求可拆分VRP及混沌遗传模拟退火算法

综合考虑客户需求量允许被拆分、配送系统拥有多个配送中心且车辆可就近返回配送中心的运输模式,建立以配送中心日均建设成本、车辆派遣成本、理货成本和油耗成本之和最小为目标的数学模型,并根据问题特征设计了混沌遗传模拟退火算法对问题进行求解。通过对不同规模以及不同类型的算例进行实验,验证了混沌遗传模拟退火算法求解本文问题的有效性。     

A new mixed integer linear model for a rich vehicle routing problem with docking constraints

In this paper we address a rich vehicle routing problem that arises in real-life applications. Among other aspects we consider time windows, simultaneous delivery and pick-up at customer locations and multiple use of vehicles. To guarantee a coordinated material flow at the depot, we include the timed allocation of vehicles to loading bays at which the loading and unloading activities can occur. The resulting vehicle routing problem is formulated as a two-index vehicle-flow model which integrates the routing under real-life conditions and the assignment of vehicles to loading bays at the depot. We use CPLEX 11.0 to solve medium-sized instances that are derived from the extended Solomon test set. The selective implementation of preprocessing techniques and cutting planes improves the solver performance significantly.     

A multi-objective mathematical model for the industrial hazardous waste location-routing problem

Industrial hazardous waste management involves the collection, transportation, treatment, recycling and disposal of industrial hazardous materials that pose risk to their surroundings. In this paper, a new multi-objective location-routing model is developed, and implemented in the Marmara region of Turkey. The aim of the model is to help decision makers decide on locations of treatment centers utilizing different technologies, routing different types of industrial hazardous wastes to compatible treatment centers, locations of recycling centers and routing hazardous waste and waste residues to those centers, and locations of disposal centers and routing waste residues there. In the mathematical model, three criteria are considered: minimizing total cost, which includes total transportation cost of hazardous materials and waste residues and fixed cost of establishing treatment, disposal and recycling centers; minimizing total transportation risk related to the population exposure along transportation routes of hazardous materials and waste residues; and minimizing total risk for the population around treatment and disposal centers, also called site risk. A lexicographic weighted Tchebycheff formulation is developed and computed with CPLEX software to find representative efficient solutions to the problem. Data related to the Marmara region is obtained by utilizing Arcview 9.3 GIS software and Marmara region geographical database.     

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.     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.