A parallel clustering technique for the vehicle routing problem with split deliveries and pickups

In this paper, a parallel clustering technique and route construction heuristic have been developed for the vehicle routing problem (VRP) with split deliveries and pickups. An MILP formulation for determining the exact solution to the problem has also been included. It has been shown through extensive experimentation that the algorithm proposed in this paper statistically produces better results than the only heuristic existing for this class of problems in literature. We also form a basis of comparison between this class of problems and the VRP with simultaneous deliveries and pickups. We note that while heuristics for simultaneous deliveries and pickups cannot be applied in situations where customers' delivery or pickup demands exceed the vehicle capacity, heuristics allowing split deliveries and pickups can, in fact, be applied in every situation, even producing superior results under the combined objective of minimization of the fixed charge and mileage associated with vehicle routes. A guideline as to which heuristic could be used under what parametric conditions and objective functions, has also been provided.     

Heuristics for the lexicographic max-ordering vehicle routing problem

In this paper, we propose fast heuristics for the vehicle routing problem (VRP) with lexicographic max-order objective. A fixed number of vehicles, which are based at a depot, are to serve customers with known demands. The lexicographic max-order objective is introduced by asking to minimize lexicographically the sorted route lengths. Based on a model for this problem, several approaches are studied and new heuristic solution procedures are discussed resulting in the development of a sequential insertion heuristic and a modified savings algorithm in several variants. Comparisons between the algorithms are performed on instances of the VRP library VRPLIB. Finally, based on the results from the computational experiments, conclusions about the applicability and efficiency of the presented algorithms are drawn.     

A Repeated Matching Heuristic for the Vehicle Routeing Problem

A new heuristic for the vehicle routeing problem which makes use of repeated matching is described. The numerical results are comparable to or better than the best published for most of the 14 benchmark problems commonly used to evaluate VRP heuristics.     

Experience with a framework for developing heuristics for solving rich vehicle routing problems

According to Cordeau et al. (J Oper Res Soc 53(5):512–522, 2002) a good VRP heuristic should fulfill four criteria: accuracy, speed, simplicity, and flexibility. In this paper we report experience with a heuristic framework for solving rich vehicle routing problems (RVRP), which is based on rather simple heuristics. This heuristic framework has been implemented as flexible software framework. The user-friendly design enables flexible customization of problem-specific solvers. Our computational study on five RVRP reveals that the heuristic approach is rather robust with respect to parameterization and that the solvers which have been customized from the framework can compete with state-of-the-art special purpose developments.     

改进蚁群算法优化周期性车辆路径问题

周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T＞1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。     

A library of local search heuristics for the vehicle routing problem

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.     

共享单车再平衡问题及其容差插入启发式算法

共享单车再平衡问题是一类NP-难问题,已有启发式求解算法随着问题规模扩大求解速度显著变慢。本文先讨论了该问题的线路可行变换性质,推导证明了插入构造可行解时,被插入位置允许插入客户点的容量区间。在此基础上,提出容差概念,设计了容差插入启发式算法,对该算法应用标准算例测试表明,算法速度快,参数设置简单;算法找到11个测试算例的当前最好解,其中1个为新的当前最好解;算法求解大容量问题的质量优于中、小容量问题。     

Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case

The basic Vehicle Routing Problem (VRP) consists of computing a set of trips of minimum total cost, to deliver fixed amounts of goods to customers with a fleet of identical vehicles. Few papers address the case with several types of vehicles (heterogeneous fleet). Most of them assume an unlimited number of vehicles of each type, to dimension the fleet from a strategic point of view. This paper tackles the more realistic tactical or operational case, with a fixed number of vehicles of each type, and the optional possibility for each vehicle to perform several trips. It describes several heuristics, including a very efficient one that progressively merges small starting trips, while ensuring that they can be performed by the fleet. This heuristic seeks to minimize the number of required vehicles as a secondary objective. It outperforms classical VRP heuristics, can easily handle various constraints, and gives very good initial solutions for a tabu search method. The real case of a French manufacturer of furniture with 775 destination stores is presented.     

Min–Max vs. Min–Sum Vehicle Routing: A worst-case analysis

The classical objective function of the Vehicle Routing Problem (VRP) is to minimize the total distance traveled by all vehicles (Min–Sum). In several situations, such as disaster relief efforts, computer networks, and workload balance, the minimization of the longest route (Min–Max) is a better objective function. In this paper, we compare the optimal solution of several variants of the Min–Sum and the Min–Max VRP, from the worst-case point of view. Our aim is two-fold. First, we seek to motivate the design of heuristic, metaheuristic, and matheuristic algorithms for the Min–Max VRP, as even the optimal solution of the classical Min–Sum VRP can be very poor if used to solve the Min–Max VRP. Second, we aim to show that the Min–Max approach should be adopted only when it is well-justified, because the corresponding total distance can be very large with respect to the one obtained by optimally solving the classical Min–Sum VRP.     

Scheduling multi-stage parallel-processor services to minimize average response time

The problem of scheduling on a multi-stage parallel-processor architecture in computer centres is addressed with the objective of minimizing average completion time of a set of requests. The problem is modelled as a flexible flowshop problem for which few heuristics exist in the flowshop scheduling literature. A new three-phase heuristic is proposed in this paper. An extensive computational experiment has been conducted to compare the performance of the existing heuristics and the proposed heuristic. The results indicate that the proposed heuristic significantly outperforms the existing ones. More specifically, the overall average error of the best existing heuristic is about five times that of the proposed heuristic while the overall average CPU time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (of the best existing to the proposed heuristic) of about five times remains almost the same.     

An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs

The problem of scheduling in a flowshop is considered with the objective of minimizing the total weighted flowtime of jobs. A heuristic algorithm is developed by the introduction of lower bounds on the completion times of jobs and the development of heuristic preference relations for the scheduling problem under study. An improvement scheme is incorporated in the heuristic to enhance the quality of its solution. The proposed heuristic, with and without the improvement scheme, and the existing heuristics are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that both versions of the proposed heuristic perform better than the existing heuristics in giving a superior solution quality and that the proposed heuristic without the improvement scheme yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the proposed heuristic and the existing heuristics, as well as the effectiveness of a variant of the scheme. The results are also discussed.     

A self-tuning heuristic for a multi-objective vehicle routing problem

In this study, a heuristic free from parameter tuning is introduced to solve the vehicle routing problem (VRP) with two conflicting objectives. The problem which has been presented is the designing of optimal routes: minimizing both the number of vehicles and the maximum route length. This problem, even in the case of its single objective form, is NP-hard. The proposed self-tuning heuristic (STH) is based on local search and has two parameters which are updated dynamically throughout the search process. The most important advantage of the algorithm is the application convenience for the end-users. STH is tested on the instances of a multi-objective problem in school bus routing and classical vehicle routing. Computational experiments, when compared with the prior approaches proposed for the multi-objective routing of school buses problem, confirm the effectiveness of STH. STH also finds high-quality solutions for multi-objective VRPs.     

Using a TSP heuristic for routing order pickers in warehouses

In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin–Kernighan–Helsgaun) TSP heuristic. Additionally, we examine if combining problem-specific solution concepts from dedicated heuristics with high-quality local search features could be useful. Lastly, we verify whether the sophistication of ‘state-of-the-art’ local search heuristics is necessary for routing order pickers in warehouses, or whether a subset of features suffices to generate high-quality solutions.     

The min-max multi-depot vehicle routing problem: heuristics and computational results

In the multi-depot vehicle routing problem (MDVRP), there are several depots where vehicles can start and end their routes. The objective is to minimize the total distance travelled by all vehicles across all depots. The min-max multi-depot vehicle routing problem (Min-Max MDVRP) is a variant of the standard MDVRP. The primary objective is to minimize the length of the longest route. We develop a heuristic (denoted by MD) for the Min-Max MDVRP that has three stages: (1) simplify the multi-depot problem into a single depot problem and solve the simplified problem; (2) improve the maximal route; (3) improve all routes by exchanging customers between routes. MD is compared with two alternative heuristics that we also develop and an existing method from the literature on a set of 20 test instances. MD produces 15 best solutions and is the top performer. Additional computational experiments on instances with uniform and non-uniform distributions of customers and varying customer-to-vehicle ratios and with real-world data further demonstrate MD’s effectiveness in producing high-quality results.     

Greedy algorithm for the general multidimensional knapsack problem

In this paper, we propose a new greedy-like heuristic method, which is primarily intended for the general MDKP, but proves itself effective also for the 0-1 MDKP. Our heuristic differs from the existing greedy-like heuristics in two aspects. First, existing heuristics rely on each item’s aggregate consumption of resources to make item selection decisions, whereas our heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criterion to make item selection decisions. Second, other methods increment the value of each decision variable only by one unit, whereas our heuristic adds decision variables to the solution in batches and consequently improves computational efficiency significantly for large-scale problems. We demonstrate that the new heuristic significantly improves computational efficiency of the existing methods and generates robust and near-optimal solutions. The new heuristic proves especially efficient for high dimensional knapsack problems with small-to-moderate numbers of decision variables, usually considered as “hard” MDKP and no computationally efficient heuristic is available to treat such problems. Supported in part by the NSF grant DMI 9812994.     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

A simple and efficient tabu search heuristic for solving the open vehicle routing problem

The open vehicle routing problem (VRP) is an immediate variant of the standard vehicle routing problem where the vehicle need not return to the depot after servicing its last customer. In this paper, we present results on an implementation of the attribute-based hill climber heuristic to the open VRP. The attribute-based hill climber heuristic is a parameter-free variant of the tabu search principle and has shown to be highly effective for the standard vehicle routing problem.     

Using a Hybrid Evolutionary Algorithm to Minimize Variance in Response Time for Multimedia Object Requests

This research addresses the scheduling problem of multimedia object requests, which is an important problem in information systems, in particular, for World Wide Web applications. The performance measure considered is the variance of response time which is crucial as end users expect fair treatment to their service requests. This problem is known to be NP-hard. The literature survey indicates that two heuristics have been proposed to solve the problem. In this paper, we present a new heuristic, a hybrid evolutionary heuristic, which is shown to perform much better than the two existing ones, e.g., the overall average errors of the existing ones are 1.012 and 2.042 while the error of the proposed hybrid evolutionary heuristic is 0.154.     

A multi-heuristic approach for solving the pre-marshalling problem

Minimizing the number of reshuffling operations at maritime container terminals incorporates the pre-marshalling problem (PMP) as an important problem. Based on an analysis of existing solution approaches we develop new heuristics utilizing specific properties of problem instances of the PMP. We show that the heuristic performance is highly dependent on these properties. We introduce a new method that exploits a greedy heuristic of four stages, where for each of these stages several different heuristics may be applied. Instead of using randomization to improve the performance of the heuristic, we repetitively generate a number of solutions by using a combination of different heuristics for each stage. In doing so, only a small number of solutions is generated for which we intend that they do not have undesirable properties, contrary to the case when simple randomization is used. Our experiments show that such a deterministic algorithm significantly outperforms the original nondeterministic method. The improvement is twofold, both in the quality of found solutions, and in the computational effort.