A variable neighborhood descent algorithm for a real waste collection problem with mobile depots

We consider a waste collection problem encountered in Due Carrare, a town located in Northern Italy. The original feature of the problem consists in the need for arranging appointments between vehicles along their routes so that small vehicles can dump their contents in the large ones and continue their work. This feature identifies the problem as a generalization of the well‐known Capacitated Arc Routing Problem (CARP). We propose a local search heuristic obtained from a variable neighborhood procedure suggested by Hertz and Mittaz (2001) for the CARP. In the Due Carrare instance, the proposed algorithm decreases the total route duration, apart from the required time for any feasible set of routes, of about 30% with respect to the routes so far adopted.     

Large neighborhood search for the bike request scheduling problem

This paper introduces an efficient algorithm for the bike request scheduling problem (BRSP). The BRSP is built around the concept of request, defined as the pickup or dropoff of a number of identical items (bikes) at a specific station, within a certain time window, and with a certain priority. The aim of the BRSP is to sequence requests on (and hence determine the routes of) a set of vehicles, in such a way that the sum of the priorities of the executed requests is maximized, all time windows are respected, and the capacity of the vehicles is not exceeded. The generation of the set of requests is explicitly not a part of the problem definition of the BRSP. The primary application of the BRSP, from which it derives its name, is to determine the routes of a set of repositioning vehicles in a bike sharing system, although other applications exist. The algorithm introduced in this paper is based on a set of related greedy randomized adaptive search procedure followed by variable neighborhood descent (GRASP + VND) operators embedded in a large neighborhood search (LNS) framework. Since this paper presents the first heuristic for the BRSP, a computational comparison to existing approaches is not possible. We therefore compare the solutions found by our LNS heuristic to those found by an exact solver (Gurobi). These experiments confirm that the proposed algorithm scales to realistic dimensions and is able to find near‐optimal solutions in seconds.     

An integration of mixed VND and VNS: the case of the multivehicle covering tour problem

The multivehicle covering tour problem (m‐CTP) is a transportation problem with different kinds of locations, where a set of locations must be visited while another set must be close enough to planned routes. Given two sets of vertices V and W, where V represents the set of vertices that may be visited and W is a set of vertices that must be covered by up to m vehicles, the m‐CTP problem is to minimize vehicle routes on a subset of V including T, which represents the subset of vertices that must be visited through the use of potential locations in V. The variant of m‐CTP without a route‐length constraint is treated in this paper. To tackle this problem, we propose a variable neighborhood search heuristic based on variable neighborhood descent method. Experiments were conducted using the datasets based on traveling salesman problem library instances.     

Variable neighborhood search to solve the generalized orienteering problem

This paper presents a variable neighborhood search (VNS) algorithm to solve the extension of the orienteering problem known as the generalized orienteering problem (GOP). Our algorithm aims to use a reduced number of neighborhoods without compromising the quality of the results. This reduced number of neighborhoods, together with the precalculation of scores associated with points of interest, allows us, in most cases, to outperform all previous metaheuristics proposed for this problem. This is the first time a VNS is being applied to the GOP, and it provides promising computational results. In particular, in the case studies considered in the paper, we were able to find 35 new best solutions, all of which were found using a shorter computational time. Furthermore, the information regarding other best‐known solutions provided in the literature has also been improved, with corrections to some previously published errors regarding scores and distances. In addition, the benchmark has been extended with the incorporation of new case studies based on real data from three of the most popular tourist cities in Spain.     

A two-level self-adaptive variable neighborhood search algorithm for the prize-collecting vehicle routing problem

This paper investigates the prize-collecting vehicle routing problem (PCVRP), which has a strong background in practical industries. In the PCVRP, the capacities of all available vehicles are not sufficient to satisfy the demands of all customers. Consequently it is not a compulsory requirement that all customers should be visited. However, a prize can be collected once a customer is visited. In addition, it is required that the total demands of visited customers should reach a pre-specified value at least. The objective is to establish a schedule of vehicle routes so as to minimize the total transportation cost and at the same time maximize the prize collected by all vehicles. The total transportation cost consists of the total distance of vehicle routes and the sum of vehicles used in the schedule. To solve the PCVRP, a two-level self-adaptive variable neighborhood search (TLSAVNS) algorithm is developed according to the two levels of decisions in the PCVRP, namely the selection of customers to visit and the visiting sequence of selected customers in each vehicle route. The proposed TLSAVNS algorithm is self-adaptive because the neighborhoods and their search sequence are determined automatically by the algorithm itself based on the analysis of its search history. In addition, a graph extension method is adopted to obtain the lower bound for PCVRP by transforming the proposed mixed integer programming model of PCVRP into an equivalent traveling salesman problem (TSP) model, and the obtained lower bound is used to evaluate the proposed TLSAVNS algorithm. Computational results on benchmark problems show that the proposed TLSAVNS algorithm is efficient for PCVRP.     

极大熵和声搜索算法求解多目标优化*

给出了求解多目标优化问题的一个新算法。首先利用极大熵函数,将多目标优化问题转换为一个单目标优化问题;然后利用和声搜索算法对其进行求解,进而得到多目标优化问题的有效解。该算法对目标函数的解析性质没有要求且容易实现,数值结果表明了该方法是有效的。     

Parallel variable neighborhood search for the min–max order batching problem

Warehousing is a key part of supply chain management. It primarily focuses on controlling the movement and storage of materials within a warehouse and processing the associated transactions, including shipping, receiving, and picking. From the tactical point of view, the main decision is the storage policy, that is, to decide where each product should be located. Every day a warehouse receives several orders from its customers. Each order consists of a list of one or more items that have to be retrieved from the warehouse and shipped to a specific customer. Thus, items must be collected by a warehouse operator. We focus on situations in which several orders are put together into batches, satisfying a fixed capacity constraint. Then, each batch is assigned to an operator, who retrieves all the items included in those orders grouped into the corresponding batch in a single tour. The objective is then to minimize the maximum retrieving time for any batch. In this paper, we propose a parallel variable neighborhood search algorithm to tackle the so‐called min–max order batching problem. We additionally compare this parallel procedure with the best previous approach. Computational results show the superiority of our proposal, confirmed with statistical tests.     

A two-phase hybrid heuristic algorithm for the capacitated location-routing problem

In this paper, we propose a two-phase hybrid heuristic algorithm to solve the capacitated location-routing problem (CLRP). The CLRP combines depot location and routing decisions. We are given on input a set of identical vehicles (each having a capacity and a fixed cost), a set of depots with restricted capacities and opening costs, and a set of customers with deterministic demands. The problem consists of determining the depots to be opened, the customers and the vehicles to be assigned to each open depot, and the routes to be performed to fulfill the demand of the customers. The objective is to minimize the sum of the costs of the open depots, of the fixed cost associated with the used vehicles, and of the variable traveling costs related to the performed routes. In the proposed hybrid heuristic algorithm, after a Construction phase (first phase), a modified granular tabu search, with different diversification strategies, is applied during the Improvement phase (second phase). In addition, a random perturbation procedure is considered to avoid that the algorithm remains in a local optimum for a given number of iterations. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several solutions obtained by the previously published methods and new best known solutions.     

独立任务分配的贪婪随机自适应搜索过程

提出了一种贪婪随机自适应搜索过程求解异构环境下的独立任务分配问题。使用随机化的最小最小完成时间算法来产生问题的初始解,再通过变邻域下降算法来改进这个解,在变邻域下降算法中,为增强算法的空间勘探能力,外层局部搜索采用允许接收劣质解的策略,使用禁忌表来防止迂回搜索,使算法在多样性和集中性间取得了较好的平衡。与领域中的典型算法进行了仿真比较,结果表明提出的算法具有良好的性能。     

A tabu search algorithm for the min–max k-Chinese postman problem

In this paper we present a tabu search algorithm for the min–max k-Chinese postman problem (MM k-CPP). Given an undirected edge-weighted graph and a distinguished depot node, the MM k  -CPP consists of finding k>1$k>1$ tours (starting and ending at the depot node) such that each edge is traversed by at least one tour and the length of the longest tour is minimized. A special emphasis is put on investigating the trade-off between running time effort and solution quality when applying different improvement procedures in the course of the neighborhood construction. Furthermore, different neighborhoods are analyzed. Extensive computational results show that the tabu search algorithm outperforms all known heuristics and improvement procedures.     

改进蚁群算法求解同型机任务调度问题

针对并行与分布式系统中的同型机调度问题,提出了一种改进蚁群算法。结合问题具体特点,给出了蚂蚁分配方案的生成策略,设计了一种新颖的基于任务适合度的信息素表示方法,以实现信息素的有效累积;改进了状态转移规则,通过对阈值的自适应调整使算法能根据搜索进度确定查找区域;在对信息素全局更新前,对每轮迭代获得的最好解进行变邻域搜索,避免算法陷入局部最优,提高收敛速度。仿真结果表明,改进算法有较强的寻优能力和稳定的求解质量。     

一种新的离散粒子群算法在指派问题中的应用

指派问题在组合优化中属NP-Complete问题。提出了一种基于离散粒子群算法的求解方法。算法中每个粒子的位置代表了一种可行的指派方案,在迭代中通过交叉策略和局部搜索策略来更新粒子的位置,这既保证了粒子位置的可行性,又增加了粒子的多样性,避免陷入早熟收敛。通过实例仿真可以看出DPSO算法简洁,较以往算法具有更好的收敛性,能得到更优的解,能够求解匈牙利法不能求解的指派问题。对不同的问题,通过影响参数的调整,可以取得好的收敛效果。     

A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints

This paper introduces a special vehicle routing problem, i.e. the cumulative capacitated vehicle routing problem with time-window constraints (Cum-CVRPTW). The problem can be defined as designing least-cost delivery routes from a depot to a set of geographically-scattered customers, subject to the constraint that each customer has to be served within a time window; accordingly, the objective costs are computed as the sum of arrival times at all the customers. The Cum-CVRPTW finds practical utility in many situations, e.g. the provision of humanitarian aids in the context of natural disasters. The Cum-CVRPTW can be viewed as a combination of two NP-hard problems, i.e. the vehicle routing problem with time windows and the cumulative vehicle routing problem. To effectively address this problem, an effective algorithm is designed, which is based on the frameworks of Large Neighborhood Search Algorithm and hybridizes with Genetic Algorithm. The proposed algorithm adopts a constraint-relaxation scheme to extend the search space, enabling the iterative exploration of both the feasible and infeasible neighborhood solutions of an incumbent solution. Furthermore, some speed-up techniques are designed to reduce the computational complexity. To elucidate its effectiveness, the proposed algorithm is examined on the benchmark instances from the literature. The resultant numerical findings show that the algorithm is able to improve and obtain some best-known solutions found by existing state-of-the-art methods.     

同时送取货选址路径问题及混合免疫算法

研究了同时送取货的选址路径问题(location-routing problem with simultaneous pickup and delivery,LRP-SPD),在同时送取货问题中,每个客户都有送货需求和取货需求,并且两种需求需要同时进行服务.在此条件下,建立了以仓库的选址成本、车辆启用成本及运输成本等目标和最小的选址路径模型;针对该模型的特点,设计改进了一种混合免疫优化算法(hybrid immune algorithm,HIA)对该问题进行求解,运用贪心聚类算法生成初始解,利用原始免疫算法对抗体进行评价排序,由邻域搜索操作改进原始算法的免疫操作.最后,通过使用混合免疫优化算法与原始免疫优化算法、模拟退火算法、蚁群算法分别对案例进行求解和对比分析,验证了提出模型的可行性和算法的有效性.     

校车路径问题的改进迭代局部搜索算法

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋以一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。     

A variable neighborhood search simheuristic for the multiperiod inventory routing problem with stochastic demands

The inventory routing problem (IRP) combines inventory management and delivery route‐planning decisions. This work presents a simheuristic approach that integrates Monte Carlo simulation within a variable neighborhood search (VNS) framework to solve the multiperiod IRP with stochastic customer demands. In this realistic variant of the problem, our goal is to establish the optimal refill policies for each customer–period combination, that is, those individual refill policies that minimize the total expected cost over the periods. This cost is the aggregation of both expected inventory and routing costs. Our simheuristic algorithm allows to consider the inventory changes between periods generated by the realization of the random demands in each period, which have an impact on the quantities to be delivered in the next period and, therefore, on the associated routing plans. A range of computational experiments are carried out in order to illustrate the potential of our simulation–optimization approach.     

Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent

The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.     

A GRASP with evolutionary path relinking for the truck and trailer routing problem

In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.     

基于图染色问题的混合优化算法

为了提高图染色算法的寻优能力和收敛速度,结合禁忌搜索算法和遗传算法的优缺点,提出了一种混合优化算法（GA-HM）。该算法利用遗传算法生成初始解,将染色元素分到不同的色集中,然后通过禁忌算法进行变领域搜索来更新顶点染色。实验结果表明,GA-HM对求解相同的目标解具有更好的全局最优性和收敛性。