A simulated annealing heuristic for the capacitated location routing problem

The location routing problem (LRP) is a relatively new research direction within location analysis that takes into account vehicle routing aspects. The goal of LRP is to solve a facility location problem and a vehicle routing problem simultaneously. We propose a simulated annealing (SA) based heuristic for solving the LRP. The proposed SALRP heuristic is tested on three sets of well-known benchmark instances and the results are compared with other heuristics in the literature. The computational study indicates that the proposed SALRP heuristic is competitive with other well-known algorithms.     

多约束选址—路径问题的改进混合遗传算法研究

选址—路径问题(LRP)同时解决设施选址和车辆路径问题,使物流系统总成本达到最小,在集成化物流配送网络规划中具有重要意义。针对带仓库容量约束和路径容量约束的选址—路径(CLRP)问题,提出了一种结合模拟退火算法的混合遗传算法进行整体求解。改进混合遗传算法分别对初始种群生成方式、遗传操作和重组策略进行改进,并实现了模拟退火的良好局部搜索能力与遗传算法的全局搜索能力的有效结合。运用一组Barreto Benchmark算例进行数值实验测试其性能,并将求解结果与国外文献中的启发式算法进行比较,验证了改进混合算法的有效性和可行性。     

A fuzzy clustering-based hybrid method for a multi-facility location problem

A fuzzy clustering-based hybrid method for a multi-facility location problem is presented in this study. It is assumed that capacity of each facility is unlimited. The method uses different approaches sequentially. Initially, customers are grouped by spherical and elliptical fuzzy cluster analysis methods in respect to their geographical locations. Different numbers of clusters are experimented. Then facilities are located at the proposed cluster centers. Finally each cluster is solved as a single facility location problem. The center of gravity method, which optimizes transportation costs is employed to fine tune the facility location. In order to compare logistical performance of the method, a real world data is gathered. Results of existing and proposed locations are reported.     

A GRASP algorithm based new heuristic for the capacitated location routing problem

Abstract

In this paper, the capacitated location-routing problem (CLRP) is studied. CLRP is composed of two hard optimisation problems: the facility location problem and the vehicle routing problem. The objective of CLRP is to determine the best location of multiple depots with their vehicle routes such that the total cost of the solution is minimal. To solve this problem, we propose a greedy randomised adaptive search procedure. The proposed method is based on a new heuristic to construct a feasible CLRP solution, and then a local search-based simulated annealing is used as improvement phase. We have used a new technique to construct the clusters around the depots. To prove the effectiveness of our algorithm, several LRP instances are used. The results found are very encouraging.     

A biased‐randomized metaheuristic for the capacitated location routing problem

The location routing problem (LRP) involves the three key decision levels in supply chain design, that is, strategic, tactical, and operational levels. It deals with the simultaneous decisions of (a) locating facilities (e.g., depots or warehouses), (b) assigning customers to facilities, and (c) defining routes of vehicles departing from and finishing at each facility to serve the associated customers’ demands. In this paper, a two‐phase metaheuristic procedure is proposed to deal with the capacitated version of the LRP (CLRP). Here, decisions must be made taking into account limited capacities of both facilities and vehicles. In the first phase (selection of promising solutions), we determine the depots to be opened, perform a fast allocation of customers to open depots, and generate a complete CLRP solution using a fast routing heuristic. This phase is executed several times in order to keep the most promising solutions. In the second phase (solution refinement), for each of the selected solutions we apply a perturbation procedure to the customer allocation followed by a more intensive routing heuristic. Computational experiments are carried out using well‐known instances from the literature. Results show that our approach is quite competitive since it offers average gaps below 0.4% with respect to the best‐known solutions (BKSs) for all tested sets in short computational times.     

A New Formulation Approach for Location-Routing Problems

A Location-Routing Problem (LRP) combines two difficult problems, facility location and vehicle routing, and as such it is inherently hard to solve. In this paper, we propose a different formulation approach than the common arc-based product-flow (Arc-BPF) approach in the literature. We associate product amounts to the nodes of the network resulting in a node-based product-flow (Node-BPF) formulation. Our main objective is to develop LRP models with fewer constraints and variables, which can be solved more efficiently. To introduce the proposed approach, we reformulate a complex four-index Arc-BPF LRP model from the literature as a three-index Node-BPF model, which computationally outperforms the former. We then introduce a heuristic method.     

Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery

The location routing problem with simultaneous pickup and delivery (LRPSPD) is a new variant of the location routing problem (LRP). The objective of LRPSPD is to minimize the total cost of a distribution system including vehicle traveling cost, depot opening cost, and vehicle fixed cost by locating the depots and determining the vehicle routes to simultaneously satisfy the pickup and the delivery demands of each customer. LRPSPD is NP-hard since its special case, LRP, is NP-hard. Thus, this study proposes a multi-start simulated annealing (MSA) algorithm for solving LRPSPD which incorporates multi-start hill climbing strategy into simulated annealing framework. The MSA algorithm is tested on 360 benchmark instances to verify its performance. Results indicate that the multi-start strategy can significantly enhance the performance of traditional single-start simulated annealing algorithm. Our MSA algorithm is very effective in solving LRPSPD compared to existing solution approaches. It obtained 206 best solutions out of the 360 benchmark instances, including 126 new best solutions.     

An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics

In this paper, we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP). The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm outperforms existing solution methods for the 2E-VRP and achieves excellent results on the LRP.     

Battery swap station location-routing problem with capacitated electric vehicles

In this paper, we present an electric vehicles battery swap stations location routing problem (BSS–EV–LRP), which aims to determine the location strategy of battery swap stations (BSSs) and the routing plan of a fleet of electric vehicles (EVs) simultaneously under battery driving range limitation. The problem is formulated as an integer programming model under the basic and extended scenarios. A four-phase heuristic called SIGALNS and a two-phase Tabu Search-modified Clarke and Wright Savings heuristic (TS-MCWS) are proposed to solve the problem. In the proposed SIGALNS, the BSSs location stage and the vehicle routing stage are alternated iteratively, which considers the information from the routing plan while improving the location strategy. In the first phase, an initial routing plan is generated with a modified sweep algorithm, leading to the BSSs location subproblem, which is then solved by using an iterated greedy heuristic. In the third phase, the vehicle routes resulting from the location subproblem are determined by applying an adaptive large neighborhood search heuristic with several new neighborhood structures. At the end of SIGALNS, the solution is further improved by a split procedure. Compared with the MIP solver of CPLEX and TS-MCWS over three sets of instances, SIGALNS searches the solution space more efficiently, thus producing good solutions without excessive computation on the medium and large instances. Furthermore, we systematically conduct economic and environmental analysis including the comparison between basic and extended scenarios, sensitivity analysis on battery driving range and efficiency analysis about the vehicle emissions reduction when EVs are used in the logistics practice.     

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.     

The Weber problem in congested regions with entry and exit points

The Weber problem is about finding a facility location on a plane such that the total weighted distance to a set of given demand points is minimized. The facility location and access routes to the facility can be restricted if the Weber problem contains congested regions, some arbitrary shaped polygonal areas on the plane, where location of a facility is forbidden and traveling is allowed at an additional fixed cost. Traveling through congested regions may also be limited to certain entry and exit points (or gates). It is shown that the restricted Weber problem is non-convex and nonlinear under Euclidean distance metric which justifies using heuristic approaches. We develop an evolutionary algorithm modified with variable neighborhood search to solve the problem. The algorithm is applied on test instances derived from the literature and the computational results are presented.     

定位2运输路线安排问题的两阶段启发式算法

重点研究了集成化物流中一类特殊的定位一运输路线安排问题(LRP)的解决方法．LRP问题包括设施定位和运输路线优化两方面决策，属于NP-hard难题．由于问题的复杂性，提出基于假设前提的LRP模型及其两阶段启发式求解算法．该方法分两步实现：首先，采用基于最小包络聚类分析的启发式方法确定被选择的潜在设施及由每一个选中的设施所要提供服务的客户群；其次，运用带有控制开关的遗传算法求解每一确定客户类中的优化运输路线．提出利用两阶段启发式算法求解LRP问题，此方法实现容易、运算简单，一定程度上避免了遗传算法中的“局部最优现象”．仿真实验证明了该算法求解单目标LRP的有效性和准确性．     

A memetic algorithm for the capacitated location-routing problem with mixed backhauls

The design of distribution networks is one of the most important problems in supply chain and logistics management. The main elements in designing a distribution network are location and routing decisions. As these elements are interdependent in many distribution networks, the overall system cost can decrease if location and routing decisions are simultaneously tackled. In this paper, we consider a Capacitated Location-Routing Problem with Mixed Backhauls (CLRPMB) which is a general case of the capacitated location-routing problem. CLRPMB 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 the same vehicle and the overall cost is minimized. Since CLRPMB is an NP-hard problem, we propose a memetic algorithm to solve the problem. To evaluate the performance of the proposed approach, we conduct an experimental study and compare its results with the lower bounds obtained by the branch-and-cut algorithm on a set of instances derived from the literature. Computational results indicate that the proposed approach is able to find optimal or very good quality solutions in a reasonable computation time.     

Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem

In this study a fuzzy c-means clustering algorithm based method is proposed for solving a capacitated multi-facility location problem of known demand points which are served from capacitated supply centres. It involves the integrated use of fuzzy c-means and convex programming. In fuzzy c-means, data points are allowed to belong to several clusters with different degrees of membership. This feature is used here to split demands between supply centers. The cluster number is determined by an incremental method that starts with two and designated when capacity of each cluster is sufficient for its demand. Finally, each group of cluster and each model are solved as a single facility location problem. Then each single facility location problem given by fuzzy c-means is solved by convex programming which optimizes transportation cost is used to fine-tune the facility location. Proposed method is applied to several facility location problems from OR library (Osman & Christofides, 1994) and compared with centre of gravity and particle swarm optimization based algorithms. Numerical results of an asphalt producer’s real-world data in Turkey are reported. Numerical results show that the proposed approach performs better than using original fuzzy c-means, integrated use of fuzzy c-means and center of gravity methods in terms of transportation costs.     

Solving a class of facility location problems using genetic algorithms

Locating p facilities to serve a number of customers is a problem in many areas of business. The problem is to determine p facility locations such that the weighted average distance traveled from all the demand points to their nearest facility sites is minimized. A variant of the p-median problem is one in which a maximum distance constraint is imposed between the demand point and its nearest facility location, also known as the p-median problem with maximum distance constraint. In this paper, we apply a fairly new methodology known as genetic algorithms to solve a relatively large sized constrained version of the p -median problem. We present our computational experience on the use of genetic algorithms for solving the constrained version of the p-median problem using two different data sets. Our comparative experimental experience shows that this solution procedure performs quite well compared with the results obtained from existing techniques.     

A note on the truck and trailer routing problem

This study considers the relaxed truck and trailer routing problem (RTTRP), a relaxation of the truck and trailer routing problem (TTRP). TTRP is a variant of the well studied vehicle routing problem (VRP). In TTRP, a fleet of trucks and trailers are used to service a set of customers with known demands. Some customers may be serviced by a truck pulling a trailer, while the others may only be serviced by a single truck. This is the main difference between TTRP and VRP. The number of available trucks and available trailers is limited in the original TTRP but there are no fixed costs associated with the use of trucks or trailers. Therefore, it is reasonable to relax this fleet size constraint to see if it is possible to further reduce the total routing cost (distance). In addition, the resulting RTTRP can also be used to determine a better fleet mix. We developed a simulated annealing heuristic for solving RTTRP and tested it on 21 existing TTRP benchmark problems and 36 newly generated TTRP instances. Computational results indicate that the solutions for RTTRP are generally better than the best solutions in the literature for TTRP. The proposed SA heuristic is able to find better solutions to 18 of the 21 existing benchmark TTRP instances. The solutions for the remaining three problems are tied with the best so far solutions in the literature. For the 36 newly generated problems, the average percentage improvement of RTTRP solutions over TTRP solutions is about 5%. Considering the ever rising crude oil price, even small reduction in the route length is significant.     

An arc flow formulation to the multitrip production,inventory, distribution,and routing problem with time windows

The multitrip production, inventory, distribution, and routing problem with time windows (MPIDRPTW) is an integrated problem that combines a production and distribution problem, a multitrip vehicle routing problem, and an inventory routing problem. In the MPIDRPTW, a set of customers, which have a time-varying demand during a finite planning horizon, is served by a single production facility. The distribution is accomplished by a fleet of homogeneous vehicles that deliver the customer orders within their specific time windows. Production management has to be done according to the inventories at the facility and at the customers. An exact arc flow model based on a graph is proposed to solve the MPIDRPTW, where the nodes represent instants of time. The main goal of the problem is to minimize the costs associated with the entire system. The proposed approach was implemented and a set of experimental tests were conducted based on a set of adapted instances from the literature.     

Robust Facility Location Problem for Hazardous Waste Transportation

We consider a robust facility location problem for hazardous materials (hazmat) transportation considering routing decisions of hazmat carriers. Given a network and a known set of nodes from which hazmat originate, we compute the locations of hazmat processing sites (e.g. incinerators) which will minimize total cost, in terms of fixed facility cost, transportation cost, and exposure risk. We assume that hazmat will be taken to the closest existing processing site. We present an exact full enumeration method, which is useful for small or medium-size problems. For larger problems, the use of a genetic algorithm is explored. Through numerical experiments, we discuss the impact of uncertainty and robust optimization in the hazmat combined location-routing problem.     

The min-dist location selection and facility replacement queries

We propose and study a new type of location optimization problem, the min-dist location selection problem: given a set of clients and a set of existing facilities, we select a location from a given set of potential locations for establishing a new facility, so that the average distance between a client and her nearest facility is minimized. The problem has a wide range of applications in urban development simulation, massively multiplayer online games, and decision support systems. We also investigate a variant of the problem, where we consider replacing (instead of adding) a facility while achieving the same optimization goal. We call this variant the min-dist facility replacement problem. We explore two common approaches to location optimization problems and present methods based on those approaches for solving the min-dist location selection problem. However, those methods either need to maintain an extra index or fall short in efficiency. To address their drawbacks, we propose a novel method (named MND), which has very close performance to the fastest method but does not need an extra index. We then utilize the key idea behind MND to approach the min-dist facility replacement problem, which results in two algorithms names MSND and RID. We provide a detailed comparative cost analysis and conduct extensive experiments on the various algorithms. The results show that MND and RID outperform their competitors by orders of magnitude.     

Heuristic solutions to multi-depot location-routing problems

This paper presents a method for solving the multi-depot location-routing problem (MDLRP). Since several unrealistic assumptions, such as homogeneous fleet type and unlimited number of available vehicles, are typically made concerning this problem, a mathematical formulation is given in which these assumptions are relaxed. Since the inherent complexity of the LRP problem makes it impossible to solve the problem on a larger scale, the original problem is divided into two sub-problems, i.e., the location-allocation problem, and the general vehicle routing problem, respectively. Each sub-problem is then solved in a sequential and iterative manner by the simulated annealing algorithm embedded in the general framework for the problem-solving procedure. Test problems from the literature and newly created problems are used to test the proposed method. The results indicate that this method performs well in terms of the solution quality and run time consumed. In addition, the setting of parameters throughout the solution procedure for obtaining quick and favorable solutions is also suggested.Scope and purposeIn many logistic environments managers must make decisions such as location for distribution centers (DC), allocation of customers to each service area, and transportation plans connecting customers. The location-routing problems (LRPs) are, hence, defined to find the optimal number and locations of the DCs, simultaneously with the vehicle schedules and distribution routes so as to minimize the total system costs. This paper proposes a decomposition-based method for solving the LRP with multiple depots, multiple fleet types, and limited number of vehicles for each different vehicle type. The solution procedure developed is very straightforward conceptually, and the results obtained are comparable with other heuristic methods. In addition, the setting of parameters throughout the solution procedure for obtaining quick and favorable solutions is also suggested.