•We propose an effective adaptive VNS for the cumulative capacitated VRP (CCVRP).•We report extensive results with many new best solutions.•We study an alternative objective, the min-max CCVRP.•We ...present results for the min-max CCVRP for the first time.•We provide managerial insights that consider these two objective functions.
The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new variant of the classical capacitated vehicle routing problem in which the objective is to minimise the sum of arrival times at customers (min-sum) instead of the total route distance. While the literature for the CCVRP is scarce, this problem has useful applications especially in the area of supplying humanitarian aid after a natural disaster. In this paper, a two-stage adaptive variable neighbourhood search (AVNS) algorithm that incorporates large neighbourhood search (LNS) as a diversification strategy is proposed. When tested on the benchmark data sets, the results show that the proposed AVNS is highly competitive in producing new best known solutions to more than half of the instances. An alternative but related objective that minimises the maximum arrival time (min-max) is also explored in this study demonstrating the flexibility and the effectiveness of the proposed metaheuristic. To the best of our knowledge, this is the first study that exploits the min-max objective of the CCVRP in addition to providing extensive computational results for a large number of instances for the min-sum. As a by-product of this study, managerial insights for decision making are also presented.
In this paper we propose effective heuristics for the solution of the planar p-median problem. We develop a new distribution based variable neighborhood search and a new genetic algorithm, and also ...test a hybrid algorithm that combines these two approaches. The best results were obtained by the hybrid approach. The best known solution was found in 466 out of 470 runs, and the average solution was only 0.000016% above the best known solution on 47 well explored test instances of 654 and 1060 demand points and up to 150 facilities.
A hybridisation of a clustering-based technique and of a variable neighbourhood search (VNS) is designed to solve large-scale
p
-median problems. The approach is based on a multi-stage methodology ...where learning from previous stages is taken into account when tackling the next stage. Each stage is made up of several subproblems that are solved by a fast procedure to produce good feasible solutions. Within each stage, the solutions returned are put together to make up a new promising subset of potential facilities. This augmented
p
-median problem is then solved by VNS. As these problems used aggregation, a cost evaluation based on the original demand points instead of aggregation is computed for each of the ‘aggregation’-based solution. The one yielding the least cost is then selected and its chosen facilities included into the next stages. This multi-stage process is repeated several times until a certain criterion is met. This approach is enhanced by an efficient way to aggregate the data and a neighbourhood reduction scheme when allocating demand points to their nearest facilities. The proposed approach is tested, using various values of
p
, on the largest data sets from the literature with up to 89,600 demand points with encouraging results.
•An emergency response trade-off model to assist decision-makers in taking focused action was developed.•A modified Dijkstra algorithm and a minimum cost maximum flow algorithm were employed to ...determine the optimal evaluation routes.•Emergency response risk levels and multiple emergency response windows of opportunity were obtained.
When there are toxic gas leaks, rapid emergency response planning is vital to protect public safety. In this study, an emergency response trade-off model to assist decision-makers in taking focused action for different personnel is developed. First, a modified Dijkstra algorithm and a minimum cost maximum flow algorithm are employed to determine the optimal evaluation routes, after which an as low as reasonably practical criterion is applied to evaluate the emergency response risk levels and identify the multiple emergency response windows of opportunity. Finally, a case study based on a real incident is given to illustrate the applicability of our method. It was found that an immediate evacuation of all members of the public in a target area would expose some of them to excessive risk. It was also discovered that there is a close and complex relationship between the emergency response risk and the shelter-in-place duration and the public emergency response. Another interesting finding is that the evacuation routes in the windows of opportunities differ significantly depending on the location, and the emergency response risks associated with using the same path to evacuate at different times. These interesting findings, which were based on the scientific assessment of emergency response risks, have a massive practical impact and could assist in more accurately formulating public protection strategies.
This paper presents a new variant of the capacitated multi-source Weber problem that introduces fixed costs for opening facilities. Three types of fixed costs are considered and experimented upon. A ...guided constructive heuristic scheme based on the concept of restricted regions and a greedy randomized adaptive search procedure (GRASP) are proposed. The four known data sets in the literature, typically used for the uncapacitated multi-source Weber problem, are adapted by adding capacities and facility fixed costs and used as a platform to assess the performance of our proposed approaches. Computational results are provided and some research avenues highlighted.
•VNS-triggered memory extraction improves method performance up to 5.2%.•Incorporating real life aspects could improve daily total routing cost up to 8%.•Vehicle capacity and working time utilization ...could be improved by up to 12.5%.•Real life aspects could improve fleet composition at no extra cost.•Interesting managerial insights regarding real life routing trade-offs.
In this paper we consider a real life Vehicle Routing Problem inspired by the gas delivery industry in the United Kingdom. The problem is characterized by heterogeneous vehicle fleet, demand-dependent service times, maximum allowable overtime and a special light load requirement. A mathematical formulation of the problem is developed and optimal solutions for small sized instances are found. A new learning-based Population Variable Neighbourhood Search algorithm is designed to address this real life logistic problem. To the best of our knowledge Adaptive Memory has not been hybridized with a classical iterative memoryless method. In this paper we devise and analyse empirically a new and effective hybridization search that considers both memory extraction and exploitation. In terms of practical implications, we show that on a daily basis up to 8% cost savings on average can be achieved when overtime and light load requirements are considered in the decision making process. Moreover, accommodating for allowable overtime has shown to yield 12% better average utilization of the driver's working hours and 12.5% better average utilization of the vehicle load, without a significant increase in running costs. We also further discuss some managerial insights and trade-offs.
•A new variant (FSMVRPB) of the classical Vehicle Routing Problem is introduced.•A mathematical formulation, optimal solutions, lower/upper bounds are presented.•We have also developed hybrid ...heuristic based on set partitioning.•New data instances are created; results can be used for future benchmarking.
In this paper we present a new variant of the classical Vehicle Routing Problem – the Fleet Size and Mix Vehicle Routing Problem with Backhauls (FSMVRPB). An ILP formulation of the FSMVRPB is presented. Optimal solutions for small size instances are produced and upper and lower bounds are generated for larger ones. In this paper we also propose a Set Partitioning Problem (SPP) based heuristic. Three frameworks are developed and tested on a set of new FSMVRPB data instances which we generated. Computational results are presented which can be used for future benchmarking.
•A strategic location routing problem with heterogeneous fleet of electric vehicles is considered.•A mixed integer programming formulation is provided.•An exact Benders decomposition algorithm is ...developed.•Challenging small size benchmark instances are successfully solved.•Highlights of some interesting managerial insight are given.
In this paper, we focus on a problem that requires the location of recharging stations and the routing of electric vehicles in a goods distribution system. The goods are disseminated from a depot and distributed to the customers via a heterogeneous fleet of electric vehicles with limited capacity. Differently from the classical vehicle routing problem, the vehicles have battery restrictions that need to be recharged at some stations if a trip is longer than their range. The problem reduces to finding the optimal locations of the recharging stations and their number to minimize the total cost, which includes the routing cost, the recharging cost, and the fixed costs of opening stations and operating vehicles. We propose a novel mathematical formulation and an efficient Benders decomposition algorithm embedded into a two-phase general framework to solve this environmental logistics problem. Phase I solves a restricted problem to provide an upper bound for the original problem which is later solved in Phase II. Between the two phases, an intermediate processing procedure is introduced to reduce the computations of the Phase II problem. This is achieved by a combination of the Phase I upper bound and several lower bounds obtained via exploiting the underlying network structure. Our approach solves the problem in a general setting with non-identical stations and vehicles by allowing multiple visits to the stations and partial recharging. The computational study provides both managerial and methodological insights.
PDF
