有时间窗车辆路径问题的捕食搜索算法

有时间窗车辆路径问题是当前物流配送系统研究中的热点问题,该问题具有NP难性质。难以求得最优解或满意解,在建立有时间窗车辆路径问题数学模型的基础上。设计了一种模仿动物捕食策略的捕食搜索算法．该算法利用控制搜索空间的限制大小来实现算法的局域搜索和全局搜索,具有良好的局部集中搜索和跳出局部最优的能力．通过实例计算,并与相关启发式算法比较．取得了满意的结果．     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.     

Waste collection vehicle routing problem with time windows

In this paper, we address a real life waste collection vehicle routing problem with time windows (VRPTW) with consideration of multiple disposal trips and drivers’ lunch breaks. Solomon's well-known insertion algorithm is extended for the problem. While minimizing the number of vehicles and total traveling time is the major objective of vehicle routing problems in the literature, here we also consider the route compactness and workload balancing of a solution since they are very important aspects in practical applications. In order to improve the route compactness and workload balancing, a capacitated clustering-based waste collection VRPTW algorithm is developed. The proposed algorithms have been successfully implemented and deployed for the real life waste collection problems at Waste Management, Inc. A set of waste collection VRPTW benchmark problems is also presented in this paper.Waste collection problems are frequently considered as arc routing problems without time windows. However, that point of view can be applied only to residential waste collection problems. In the waste collection industry, there are three major areas: commercial waste collection, residential waste collection and roll-on-roll-off. In this paper, we mainly focus on the commercial waste collection problem. The problem can be characterized as a variant of VRPTW since commercial waste collection stops may have time windows. The major variation from a standard VRPTW is due to disposal operations and driver's lunch break. When a vehicle is full, it needs to go to one of the disposal facilities (landfill or transfer station). Each vehicle can, and typically does, make multiple disposal trips per day. The purpose of this paper is to introduce the waste collection VRPTW, benchmark problem sets, and a solution approach for the problem. The proposed algorithms have been successfully implemented and deployed for the real life waste collection problems of Waste Management, the leading provider of comprehensive waste management services in North America with nearly 26,000 collection and transfer vehicles.     

A genetic algorithm for the simultaneous delivery and pickup problems with time window

This paper concerns a Simultaneous Delivery and Pickup Problem with Time Windows (SDPPTW). A mixed binary integer programming model was developed for the problem and was validated. Due to its NP nature, a co-evolution genetic algorithm with variants of the cheapest insertion method was proposed to speed up the solution procedure. Since there were no existing benchmarks, this study generated some test problems which revised from the well-known Solomon’s benchmark for Vehicle Routing Problem with Time Windows (VRPTW). From the comparison with the results of Cplex software and the basic genetic algorithm, the proposed algorithm showed that it can provide better solutions within a comparatively shorter period of time.     

Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows

In this paper a model and several solution procedures for a novel type of vehicle routing problems where time windows for the pickup of perishable goods depend on the dispatching policy used in the solution process are presented. This problem is referred to as Vehicle Routing Problem with multiple interdependent time windows (VRPmiTW) and is motivated by a project carried out with the Austrian Red Cross blood program to assist their logistics department. Several variants of a heuristic constructive procedure as well as a branch-and-bound based algorithm for this problem were developed and implemented. Besides finding the expected reduction in costs when compared with the current procedures of the Austrian Red Cross, the results show that the heuristic algorithms find solutions reasonably close to the optimum in fractions of a second. Another important finding is that increasing the number of pickups at selected customers beyond the theoretical minimum number of pickups yields significantly greater potential for cost reductions.     

Vehicle routing problem with a heterogeneous fleet and time windows

In this paper, a problem variant of the vehicle routing problem with time windows is introduced to consider vehicle routing with a heterogeneous fleet, a limited number of vehicles and time windows. A method that extends an existing tabu search procedure to solve the problem is then proposed. To evaluate the performance of the proposed method, experiments are conducted on a large set of test cases, which comprises several benchmark problems from numerous problem variants of the vehicle routing problem with a heterogeneous fleet. It is observed that the proposed method can be used to give reasonably good results for these problem variants. In addition, some ideas are presented to advance the research in heuristics, such as fair reporting standards, publication of benchmark problems and executable routines developed for algorithmic comparison.     

A Coordination-Based Algorithm for Dedicated Destination Vehicle Routing in B2B E-Commerce

This paper proposes a solution to the open vehicle routing problem with time windows (OVRPTW) considering third-party logistics (3PL). For the typical OVRPTW problem, most researchers consider time windows, capacity, routing limitations, vehicle destination, etc. Most researchers who previously investigated this problem assumed the vehicle would not return to the depot, but did not consider its final destination. However, by considering 3PL in the B2B e-commerce, the vehicle is required back to the nearest 3PL location with available space. This paper formulates the problem as a mixed integer linear programming (MILP) model with the objective of minimizing the total travel distance. A coordinate representation particle swarm optimization (CRPSO) algorithm is developed to obtain the best delivery sequencing and the capacity of each vehicle. Results of the computational study show that the proposed method provides solution within a reasonable amount of time. Finally, the result compared to PSO also indicates that the CRPSO is effective.     

The vehicle routing problem with multiple prioritized time windows: A case study

This paper addresses Multi-objective Vehicle Routing Problem with Multiple Prioritized Time Windows (VRPMPTW) in which the distributer proposes a set of all non-overlapping time windows with equal or different lengths and the customers prioritize these delivery time windows. VRPMPTW aims to find a set of routes of minimal total traveling cost and maximal customer satisfaction (with regard to the prioritized time windows), starting and ending at the depot, in such a way that each customer is visited by one vehicle given the capacity of the vehicle to satisfy a specific demand. This problem is inspired from a real life application. The contribution of this paper lies in its addressing the VRPMPTW from a problem definition, modeling and methodological point of view. We developed a mathematical model for this problem. This model can simply be used for a wide range of applications where the customers have multiple flexible time windows and violation of time windows may drop the satisfaction levels of customers and lead to profit loss in the long term. A Cooperative Coevolutionary Multi-objective Quantum-Genetic Algorithm (CCMQGA) is also proposed to solve this problem. A new local search is designed and used in CCMQGA to reach an appropriate pareto front. Finally, the proposed approach is employed in a real case study and the results of the proposed CCMQGA are compared with the current solution obtained from managerial experience, the results of NSGA-II and the multi-objective quantum-inspired evolutionary algorithm.     

改进蚁群算法求解有时间窗的物流配送路径问题

物流配送车辆路径优化问题已被证明是一个NP难题,很难得到最优解。应用蚁群算法对带时间窗的物流车辆路径优化问题进行了算法设计,建立了车辆路径优化问题的蚁群算法数学模型及解决方案。通过对蚁群算法的分析,提出了改进的蚁群算法,并结合实例对该算法进行测试和分析,检验其有效性,结果表明了改进蚁群算法的可行性,符合实际的需要。     

A constraint programming approach to the Chinese postman problem with time windows

The Chinese postman problem with time windows (CPPTW) is modelled as a constraint programme and results are reported for a set of test problems with up to 69 edges. Two different formulations are proposed. The first formulation approaches the problem directly and the second transforms the problem to an equivalent vehicle routing problem with time windows. The results demonstrate that optimal solutions can be obtained quickly when the time windows are tight. However, the results also show that as the time windows are made wider and the number of feasible solutions increases, these constraint programming formulations take significantly longer to find a provably optimal solution. The results also demonstrate how the size and density of the graph affects the computing time needed to find an optimal solution.     

A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows

The Capacitated Vehicle Routing Problem with Time Windows is an important combinatorial optimization problem consisting in the determination of the set of routes of minimum distance to deliver goods, using a fleet of identical vehicles with restricted capacity, so that vehicles must visit customers within a time frame. A large number of algorithms have been proposed to solve single-objective formulations of this problem, including meta-heuristic approaches, which provide high quality solutions in reasonable runtimes. Nevertheless, in recent years some authors have analyzed multi-objective variants that consider additional objectives to the distance travelled. This paper considers not only the minimum distance required to deliver goods, but also the workload imbalance in terms of the distances travelled by the used vehicles and their loads. Thus, MMOEASA, a Pareto-based hybrid algorithm that combines evolutionary computation and simulated annealing, is here proposed and analyzed for solving these multi-objective formulations of the VRPTW. The results obtained when solving a subset of Solomon’s benchmark problems show the good performance of this hybrid approach.     

Solving the Orienteering Problem with Time Windows via the Pulse Framework

The Orienteering Problem with Time Windows (OPTW) is the problem of finding a path that maximizes the profit available at the nodes in a time-constrained network. The OPTW has multiple applications in transportation, telecommunications, and scheduling. First, we extend an exact method for shortest path problems with side constraints into a general-purpose framework for hard shortest path variants. Then, using this framework, we develop a new method for the OPTW that incorporates problem-specific knowledge. Our method outperforms the state-of-the-art algorithm on instances derived from benchmark datasets from the literature achieving speedups of up to 266 times and is able to find optimal solutions to large-scale problems with up to 562 nodes in short computational times.     

Exchange strategies for multiple Ant Colony System

In this paper we apply the concept of parallel processing to enhance the performance of the Ant Colony System algorithm. New exchange strategies based on a weighting scheme are introduced under three different types of interactions. A search assessment technique based on a team consensus methodology is developed to study the influence of these strategies on the search behavior. This technique demonstrates the influence of these strategies in terms of search diversity. The performance of the Multiple Ant Colony System algorithm, applied to the Vehicle Routing Problem with Time Windows as well as the Traveling Salesman Problem, is investigated and evaluated with respect to solution quality and computational effort. The experimental studies demonstrate that the Multiple Ant Colony System outperforms the sequential Ant Colony System. The studies also indicate that the weighting scheme improves performance, particularly in strategies that share pheromone information among all colonies. A considerable improvement is also obtained by combining the Multiple Ant Colony System with a local search procedure.     

Artificial intelligence heuristics in solving vehicle routing problems with time window constraints

This paper describes the authors’ research on various heuristics in solving vehicle routing problem with time window constraints (VRPTW) to near optimal solutions. VRPTW is NP-hard problem and best solved to near optimum by heuristics. In the vehicle routing problem, a set of geographically dispersed customers with known demands and predefined time windows are to be served by a fleet of vehicles with limited capacity. The optimized routines for each vehicle are scheduled as to achieve the minimal total cost without violating the capacity and time window constraints. In this paper, we explore different hybridizations of artificial intelligence based techniques including simulated annealing, tabu search and genetic algorithm for better performance in VRPTW. All the implemented hybrid heuristics are applied to solve the Solomon's 56 VRPTW with 100-customer instances, and yield 23 solutions competitive to the best solutions published in literature according to the authors’ best knowledge.     

A novel differential evolution mapping technique for generic combinatorial optimization problems

Differential evolution is primarily designed and used to solve continuous optimization problems. Therefore, it has not been widely considered as applicable for real-world problems that are characterized by permutation-based combinatorial domains. Many algorithms for solving discrete problems using differential evolution have been proposed, some of which have achieved promising results. However, to enhance their performance, they require improvements in many aspects, such as their convergence speeds, computational times and capabilities to solve large discrete problems. In this paper, we present a new mapping method that may be used with differential evolution to solve combinatorial optimization problems. This paper focuses specifically on the mapping component and its effect on the performance of differential evolution. Our method maps continuous variables to discrete ones, while at the same time, it directs the discrete solutions produced towards optimality, by using the best solution in each generation as a guide. To judge its performance, its solutions for instances of well-known discrete problems, namely: 0/1 knapsack, traveling salesman and traveling thief problems, are compared with those obtained by 8 other state-of-the-art mapping techniques. To do this, all mapping techniques are used with the same differential evolution settings. The results demonstrated that our technique significantly outperforms the other mapping methods in terms of the average error from the best-known solution for the traveling salesman problems, and achieves promising results for both the 0/1 knapsack and the traveling thief problems.     

A lower bound for the hitting set size for combinatorial rectangles and an application

We prove a lower bound of where for the hitting set size for combinatorial rectangles of volume at least ε in [m]^d space, for and d>2.     

An evolutionary approach for multi-objective vehicle routing problems with backhauls

The vehicle routing problem (VRP) is an important aspect of transportation logistics with many variants. This paper studies the VRP with backhauls (VRPB) in which the set of customers is partitioned into two subsets: linehaul customers requiring a quantity of product to be delivered, and backhaul customers with a quantity to be picked up. The basic VRPB involves finding a collection of routes with minimum cost, such that all linehaul and backhaul customers are serviced. A common variant is the VRP with selective backhauls (VRPSB), where the collection from backhaul customers is optional. For most real world applications, the number of vehicles, the total travel cost, and the uncollected backhauls are all important objectives to be minimized, so the VRPB needs to be tackled as a multi-objective problem. In this paper, a similarity-based selection evolutionary algorithm approach is proposed for finding improved multi-objective solutions for VRPB, VRPSB, and two further generalizations of them, with fully multi-objective performance evaluation.     

Analysis of OpenMP and MPI implementations of meta-heuristics for vehicle routing problems

The parallelization of heuristic methods allows the researchers both to explore the solution space more extensively and to accelerate the search process. Nowadays, there is an increasing interest on developing parallel algorithms using standard software components that take advantage of modern microprocessors including several processing cores with local and shared cache memories. The aim of this paper is to show it is possible to parallelize algorithms included in computational software using standard software libraries in low-cost multi-core systems, instead of using expensive high-performance systems or supercomputers. In particular, it is analyzed the benefits provided by master-worker and island parallel models, implemented with MPI and OpenMP software libraries, to parallelize population-based meta-heuristics. The capacitated vehicle routing problem with hard time windows (VRPTW) has been used to evaluate the performance of these parallel strategies. The empirical results for a set of Solomon's benchmarks show that the parallel approaches executed on a multi-core processor produce better solutions than the sequential algorithm with respect to both the quality of the solutions obtained and the runtime required to get them. Both MPI and OpenMP parallel implementations are able to obtain better or at least equal solutions (in terms of distance traveled) than the best known ones for the considered benchmark instances.     

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows

The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.     

A note on robustness tolerances for combinatorial optimization problems

We consider so-called generic combinatorial optimization problem, where the set of feasible solutions is some family of nonempty subsets of a finite ground set with specified positive initial weights of elements, and the objective function represents the total weight of elements of the feasible solution. We assume that the set of feasible solutions is fixed, but the weights of elements may be perturbed or are given with errors. All possible realizations of weights form the set of scenarios.A feasible solution, which for a given set of scenarios guarantees the minimum value of the worst-case relative regret among all the feasible solutions, is called a robust solution. The maximum percentage perturbation of a single weight, which does not destroy the robustness of a given solution, is called the robustness tolerance of this weight with respect to the solution considered.In this paper we give formulae for computing the robustness tolerances with respect to an optimal solution obtained for some initial weights and we show that this can be done in polynomial time whenever the optimization problem is polynomially solvable itself.