Search

This paper addresses the transportation of valuable goods in which security carriers are interested to optimize the operating costs and the vehicle routes’ security. In real operations, route planning and scheduling are normally performed manually based on individual experience. Hereupon, an optimizing approach should be developed to target the robbery risk reduction and the distribution network’ operational costs. Facing the dangerous nature of operations, some considerations play an important role, including demand fluctuations and traffic congestion of the urban environment. To handle these issues, we respectively benefit from the robust optimization theory and considering time-dependent travel speeds with satisfying the “first-in-first-out” property. This paper proposes a rich vehicle routing problem denoted by the secure time-dependent vehicle routing problem with time windows including pickup and delivery with uncertain demands (S-TD-VRPTWPD-UD). A mathematical formulation and an efficient solution approach combining the greedy randomized adaptive search procedure (GRASP) and the iterated local search (ILS) are developed to minimize the predictability of route plans using an integrated risk index, besides the travel costs. Extensive computational experiments on this problem are performed to analyze the impact of the demand uncertainty and the speed time-dependency and to show the efficiency of the GRASP × ILS implementation. The results show the significant improvements due to the time-dependency as well as the extra cost of protecting the model against the worst-case scenario of demand requests by deriving the robust counterpart of the S-TD-VRPTWPD-UD.

As technology continues to improve people’s quality of life, there is a large, unfulfilled market worldwide for on-demand meal delivery services. The competitive edge of the business is foremost sharpened by the agility of the transport system. While lightweight drones are being developed as the next-generation vehicular platform for meal delivery, an efficient fleet operation becomes especially critical. This paper presents a mixed integer programming (MIP) model that comprehensively characterizes all relevant aspects of the business scenario, and proposes an optimization-driven, progressive algorithm for online fleet dispatch operations. Different from typical graph-based formulations of vehicle routing problems, the proposed temporally discrete and spatially continuous MIP formulation endogenously accounts for geometry and mobility and therefore permits dynamic input of order information with arbitrary pickup and delivery locations. The model is augmented with special constraints and an artificial objective function which effectively relay the system states between successive time horizons. The algorithm is validated through simulation case studies and is shown to meet the design objectives.

The vehicle routing problem derived from a real cold-chain distribution company is studied in this paper. It is formulated as a multi-compartment vehicle routing problem with some practical constraints. A mathematical model is provided and an adaptive large neighborhood search (ALNS) algorithm is developed to solve the real-world problems. The computational experiments demonstrate the effectiveness and efficiency of the ALNS algorithm compared with the manual method based mostly on experience. In addition, a sensitivity analysis provides valuable managerial insights for the decision-makers.

Recently, a growing concern with sustainability has become a consideration in business operations. However, there is a lack of mathematical models that quantify environmental effects and, in particular, social impacts of supply chains because of the inherently subjective nature of these aspects. To fill this gap, this paper models a distribution network in which the triple bottom lines of sustainability are captured. Different impacts of the network on the stakeholders, including company owners, workers, consumers and society, are considered as whole. In the current model, a multi-product vehicle routing problem with time windows (MPVRPTW) as an operational decision is integrated with strategic decisions related to the network design. To solve this model, three hybrid swarm intelligence techniques (particle swarm optimization (PSO), electromagnetism mechanism algorithm (EMA), and artificial bee colony (ABC)) are proposed, and each is hybridized with variable neighborhood search (VNS) are proposed. Because metaheuristic methods are sensitive to input parameters, response surface methodology (RSM) with the multi-objective decision making (MODM) approach is applied for tuning the parameters. The proposed approaches are compared with the hybrid of genetic algorithm (GA) and VNS as the benchmark algorithm. A fair comparison is conducted by employing six metrics to evaluate the quality of the Pareto frontier obtained by the algorithms on the test problems. According to the results, the predominance of EMA is enhanced by VNS local search.

In this paper we study the multi-period vehicle routing problem with due dates. A supplier has to determine a distribution plan to visit a set of customers over a given planning horizon. Each customer is associated with a release date and a due date, that is, the date at which the goods required by the customer become available at the supplier’s depot, and the date by which the customer has to be visited, respectively. A fleet of capacitated vehicles is available at the depot to perform the distribution and the objective is to minimize the distribution costs and the costs related to delayed deliveries. New families of valid inequalities are presented that allow us to improve a branch-and-bound algorithm proposed in the literature. The new branch-and-bound algorithm reduces to 5.1% the optimality gap which is 12.1% for the known branch-and-bound on instances with one vehicle. A variable MIP neighborhood descent (VMND) algorithm is also presented, which speeds up the search for high quality solutions through a local search heuristic embedded in the branch-and-bound algorithm. Computational tests are performed to assess the quality of the VMND algorithm against the new branch-and-bound algorithm. The computational results show that the VMND algorithm improves 35 out of 80 solutions on instances with one vehicle, reducing the average optimality gap from 5.1% to 3.6%. It further matches the performance of the new branch-and-bound algorithm on another 35 instances. On instances with two and three vehicles the average optimality gap obtained by the VMND algorithm is 5.5% and 5.6%, respectively.

With the goal of integrating drones in last-mile delivery, the Vehicle Routing Problem with Drones (VRPD) uses a fleet of vehicles, each of them equipped with a set of drones, for serving a set of customers with minimal makespan. In this paper, we propose an extension of the VRPD that we call the Vehicle Routing Problem with Drones and En Route Operations (VRPDERO). Here, in contrast to the VRPD, drones may not only be launched and retrieved at vertices but also on some discrete points that are located on each arc. We formulate the problem as a Mixed Integer Linear Program (MILP) and introduce some valid inequalities that enhance the performance of the MILP solvers. Furthermore, due to limited performance of the solvers in addressing large-scale instances, we propose an algorithm based on the concepts of Variable Neighborhood Search (VNS) and Tabu Search (TS). In order to evaluate the performance of the introduced algorithm as well as the solver in solving the VRPDERO instances, we carried out extensive computational experiments. According to the numerical results, the proposed valid inequalities and the heuristic have a significant contribution in solving the VRPDERO effectively. In addition, the consideration of en route operations can increase the utilization of drones and lead to an improved makespan.

In this paper, we address the problem of finding trajectories for multiple unmanned aerial vehicles deployed to perform a collaborative mission, requiring communication, coordination and situation awareness. Thus, we favor trajectories that are correlated in space and time, by proposing a metric to measure the dispersion between the trajectories. This dispersion metric is used as the objective function of the Minimum Dispersion Routing Problem. We propose a local search genetic algorithm as a method to solve this new routing problem, and we tested this approach using modified benchmark vehicle routing problem instances. Our computational results show that the approach is quite successful, yielding trajectories with the desired characteristics in terms of dispersion.

We consider the Green Vehicle Routing Problem (G-VRP) which is an extension of the classical vehicle routing problem for alternative fuel vehicles. In the G-VRP, vehicles' driving autonomy and possible refueling stops en-route are explicitly modeled. We propose a multi-start local search algorithm that consists of three phases. The first two phases iteratively construct new solutions, improve them by local search, and store all vehicle routes forming these solutions in a route pool. Phase three optimally combines vehicle routes in the route pool by solving a set partitioning problem and improves the final solution by local search. The algorithm is based on a multigraph reformulation of the G-VRP in which nodes correspond to customers and a depot, and arcs correspond to possible sequences of refueling stops for vehicles traveling between two nodes. All local search operators used by our algorithm are tailored to exploit this reformulation and do not explicitly deal with refueling stations. We report computational results on benchmark instances with up to ~ 470 customers, showing that the algorithm is competitive with state-of-the-art heuristics.

The vehicle routing problem is among the most-studied and practically relevant problems in combinatorial optimization. Yet, almost all research thus far has been targeted at solving problems with not more than a few hundred customers. In this paper, we explore how to design a local search heuristic that computes good solutions for very large-scale instances of the capacitated vehicle routing problem in a reasonable computational time. We investigate different ways to reduce the time complexity with pruning and sequential search, as well as the space complexity by restricting the amount of stored information. The resulting algorithm outperforms a previously introduced heuristic for instances of 10,000 and more customers in relatively short computational time. In order to stimulate more research in this domain, we introduce a new set of benchmark instances that are based on a real-world problem and contain up to 30,000 customers and use our heuristic to solve them. (C) 2019 Elsevier Ltd. All rights reserved.

Heuristics are the weapon of choice when it comes to solving complex combinatorial optimization problems. Even though a large amount of research focuses on tuning heuristics on a specific problem, little research has been done to investigate structural characteristics of the problem itself. We argue that knowledge about the structural characteristics that distinguish good from not-so-good solutions of a combinatorial optimization problem, can be instrumental in designing efficient heuristics. We develop a data-mining based approach that can generate such knowledge and apply it to the vehicle routing problem. We define several metrics to characterize both a VRP solution and a VRP instance, and generate and classify 192.000 solutions for various instances. With these metrics we are able to distinguish between optimal and non-optimal solutions with an accuracy of up to 90%. We discuss the most distinguishing characteristics of good VRP solutions, and show how the knowledge thus generated can be used to improve the performance of an existing heuristic. (C) 2018 Elsevier Ltd. All rights reserved.

Local search has been established as a successful cornerstone to tackle the Vehicle Routing Problem, and is included in many state-of-the-art heuristics. In this paper we aim to demonstrate that a well implemented local search on its own suffices to create a heuristic that computes high-quality solutions in a short time. To this end we combine three powerful local search techniques, and implement them in an efficient way that minimizes computational effort. We conduct a series of experiments to determine how local search can be effectively combined with perturbation and pruning, and make use of problem specific knowledge, to guide the search to promising solutions more effectively. The heuristic created in this way not only performs well on many benchmark sets, it is also straightforward in its design and does not contain any components of which the contribution is unclear. (C) 2019 Elsevier Ltd. All rights reserved.

We investigate a structural decomposition for the capacitated vehicle routing problem (CVRP) based on vehicle-to-customer “assignment” and visits “sequencing” decision variables. We show that an heuristic search focused on assignment decisions with a systematic optimal choice of sequences (using Concorde TSP solver) during each move evaluation is promising but requires a prohibitive computational effort. We therefore introduce an intermediate search space, based on the dynamic programming procedure of Balas & Simonetti, which finds a good compromise between intensification and computational efficiency. A variety of speed-up techniques are proposed for a fast exploration: neighborhood reductions, dynamic move filters, memory structures, and concatenation techniques. Finally, a tunneling strategy is designed to reshape the search space as the algorithm progresses. The combination of these techniques within a classical local search, as well as in the unified hybrid genetic search (UHGS) leads to significant improvements of solution accuracy. New best solutions are found for surprisingly small instances with as few as 256 customers. These solutions had not been attained up to now with classic neighborhoods. Overall, this research permits to better evaluate the respective impact of sequence and assignment optimization, proposes new ways of combining the optimization of these two decision sets, and opens promising research perspectives for the CVRP and its variants.

Unmanned aerial vehicles (UAVs) are widely used to perform monitoring tasks both in the military and civilian areas, and the planning of their routes is critical. This study investigates a routing problem in which UAVs monitor a set of areas with different accuracy requirements. This problem is a variant of the classical vehicle routing problem (VRP), where one must determine not only the order in which to visit a set of nodes located in the plane, but also the height at which to visit them, which impacts the accuracy level and the service time. An integer programming model is formulated to optimize flight routes and minimize the total time needed to complete the monitoring tasks. A tabu search metaheuristic is developed for the problem. Extensive numerical experiments are conducted to assess the efficiency of the heuristic.

Electric vehicle routing problems (E-VRPs) are receiving growing attention from the operations research community. Electric vehicles differ substantially from internal combustion engine vehicles, the main difference lying in their limited autonomy, which can be recovered at charging stations. Modeling the charging functions is a focal point of E-VRPs. Most of the research has focused on constant or linear charging functions. The E-VRP with nonlinear charging function (E-VRP-NL) was recently introduced to account for the more realistic nonlinear relationship between the time spent charging and the amount of energy charged. We propose two new formulations for this problem. We first develop an arc-based tracking of the time and the state of charge which, according to our experiments, outperforms the classical node-based tracking of these values. To avoid replicating the charging stations nodes, as done for both node and arc based formulations, we also introduce a path-based model. We develop an algorithm to generate a tractable number of these paths. This path-based model outperforms the classical models in our experiments. We also propose a new model, a heuristic, and an exact labeling algorithm for the problem of finding the optimal charging decisions for a given route. Extensive computational results show that charging decisions considerably impact the quality of the E-VRP-NL solutions. Indeed, we improve 23 out of 120 best known E-VRP-NL solutions by solely revising the charging decisions.

The Green Vehicle Routing Problem concerns routing alternative fuel vehicles, based at a single depot, to handle a subset of customers while minimizing the total travel distance. Due to limited fuel autonomy, each vehicle may need to stop at Alternative Fuel Stations (AFSs) during its trip. We propose a two-phase solution approach in which a route is seen as the composition of paths, each one handling a subset of customers without intermediate stops at AFSs. In the first phase, all feasible paths are generated limiting their number through dominance rules. In the second phase, the paths are selected and properly combined to generate the routes via Mixed Integer Linear Programming. Our approach, tested on small- to medium-sized benchmark instances, outperforms the existing exact methods obtaining always the optimal solution in a smaller average computational time. Furthermore, the approach was converted into a heuristic one considering in the first phase only a subset of feasible non-dominated paths. In this way, we can also address larger- sized instances outperforming, in terms of solution quality, the best heuristic approach in the literature.

This study addresses a multi-commodity many-to-many vehicle routing problem with simultaneous pickup and delivery (M-M-VRPSPD) for a fast fashion retailer in Singapore. Different from other widely studied pickup and delivery problems, the unique characteristics are: (1) collected products from customers are encouraged to be reallocated to fulfill demands of other customers; (2) it is multi-commodity and the number of involved commodities can be over 10,000. To solve this problem, we provide a nonvehicle-index arc-flow formulation and some strengthening strategies. Moreover, for large-scale instances, an adaptive memory programming based algorithm combined with techniques such as the regret insertion method for initializing the solution pool, the segment-based evaluation scheme, and advanced pool management method, is proposed. We test our algorithm on 66 real-world and 96 newly generated instances, and provide the results for future-use comparisons. The experiments on small-scale instances show that the proposed algorithm can quickly reach the optimality obtained by solving the mathematical formulation. In addition, the proposed algorithm is shown to perform well and stably on medium and large scale instances. Finally, we analyze some features of this problem, and find that relocation of commodities increases their utilization.

We study the integrated production and multiple trips vehicle routing problem with time windows and uncertain travel times involving two phases. The first phase considers scheduling a set of jobs on parallel machines with machine-dependent ready times, and the second phase focuses on the delivery of completed jobs by a fleet of identical vehicles, which may differ in their ready times. In addition, the travel times in distribution are uncertain. The objective is to minimize the total cost comprising the travel cost and penalty cost caused by tardiness. We present a robustness approach, known as “Elastic p-Robustness”, to deal with travel time variations when historical risk data are limited or non-existent, and develop a memetic algorithm with an effective search strategy to solve the problem. We conduct numerical studies on randomly generated data based on real experience to assess the effectiveness and efficiency of the proposed method. The computational results show that the proposed solution approach yields relatively good solutions in comparison with current mainstream heuristic algorithms.

This paper addresses a special vehicle routing problem, which extends the classical problem by considering the time window and synchronized-services constraints. A time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. This problem has many practical applications such as caregiver scheduling problem encountered in the home health care industry. The synchronization constraints in this problem interconnect various vehicles’ routes, making the problem more challenging than standard vehicle routing problem with time windows, especially in designing neighborhood search-based methods. A mixed-integer programming model is proposed for the problem. Motivated by the challenge of computational time, an efficient Adaptive Large Neighborhood Search heuristic is proposed to solve the problem. The approach is evaluated on benchmark instances acquired from the literature and new large-scale test instances first generated in this paper. The numerical results indicate that our solution method is able to outperform existing approaches.

International audience; This study addresses one of the most challenging issues in designing a sustainable and efficient ride-sharing service. This paper uses an extensive computational study to quantify the behavior of carpooling in customized bus routing problems. This mechanism allows organizations to draw on the potential of their employees’ private cars to provide convenient alternative rides for other employees, thereby reducing air pollution and greenhouse gas emissions as well as increasing overall satisfaction with the transportation system offered. The objective functions minimize: (i) total transportation costs and incentives paid to drivers of private cars, (ii) dissatisfaction as determined by staff walking distance, travel time, and delays in arriving at work, and (iii) total carbon emissions generated by commuting. We propose a resolution algorithm based on Pareto Strength Ant Colony Optimization (PSACO) as an effective meta-heuristic method for solving the multi-objective mathematical model and compare it with the results obtained by an exact method. The effectiveness and applicability of the proposed problem have been evaluated by performing computational experiments on a real case study in Paris using a number of comparative metrics with appropriate assumptions. Different parameters affecting the performance of the algorithm are also investigated. The concluding section presents a comparison of the results achieved. The test outcomes confirm that the formulation and the solution methods can be useful references for practice. The insights obtained from the research could provide the basis for designing incentive schemes and information campaigns aimed at making ride-sharing systems more successful and improving their performance.

The Vehicle Routing Problem with Discrete Split Deliveries and Pickups is a variant of the Vehicle Routing Problem with Split Deliveries and Pickups, in which customers’ demands are discrete in terms of batches (or orders). It exists in the practice of logistics distribution and consists of designing a least cost set of routes to serve a given set of customers while respecting constraints on the vehicles’ capacities. In this paper, its features are analyzed. A mathematical model and Tabu Search algorithm with specially designed batch combination and item creation operation are proposed. The batch combination operation is designed to avoid unnecessary travel costs, while the item creation operation effectively speeds up the search and enhances the algorithmic search ability. Computational results are provided and compared with other methods in the literature, which indicate that in most cases the proposed algorithm can find better solutions than those in the literature.

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension of the well-known VRPTW where electric vehicles (EVs) are used instead of internal combustion engine vehicles. An EV has a limited driving range due to its battery capacity and may need recharging to complete its route. Recharging can be made at any battery level and may be at any quantity up to the battery capacity. Furthermore, the stations may be equipped with chargers with different power supply, power voltage, maximum current options which affect the recharge duration. In this study, we model the EVRPTW by allowing partial recharges with three recharging configurations which can be referred to as normal, fast and super-fast recharges. In faster options, the battery is charged with the same energy in a shorter time but at a higher cost. Our objective is to minimize the total recharging cost while operating minimum number of vehicles. We formulated this problem as a mixed integer linear program and solved the small instances using CPLEX. To solve the larger problems, we develop a matheuristic approach which couples the Adaptive Large Neighborhood Search (ALNS) approach with an exact method. Our ALNS is equipped with various destroy-repair algorithms to efficiently explore the neighborhoods and uses CPLEX to strengthen the routes obtained. We carried out extensive experiments to investigate the benefits of fast recharges and test the performance of our algorithm using benchmark instances from the literature. The results show the effectiveness of the proposed matheuristic and demonstrate the benefits of fast chargers on the fleet size and energy costs.

The vehicle routing problem is one of the most studied combinatorial optimization topics, due to its practical importance and methodological interest. Yet, despite extensive methodological progress, many recent studies are hampered by the limited access to simple and efficient open-source solution methods. Given the sophistication of current algorithms, reimplementation is becoming a difficult and time-consuming exercise that requires extensive care for details to be truly successful. Against this background, we use the opportunity of this short paper to introduce a simple —open-source— implementation of the hybrid genetic search (HGS) specialized to the capacitated vehicle routing problem (CVRP). This state-of-the-art algorithm uses the same general methodology as Vidal et al. (2012) but also includes additional methodological improvements and lessons learned over the past decade of research. In particular, it includes an additional neighborhood called SWAP* which consists in exchanging two customers between different routes without an insertion in place. As highlighted in our study, an efficient exploration of SWAP* moves significantly contributes to the performance of local searches. Moreover, as observed in experimental comparisons with other recent approaches on the classical instances of Uchoa et al. (2017), HGS still stands as a leading metaheuristic regarding solution quality, convergence speed, and conceptual simplicity.

We introduce the two-echelon vehicle routing problem with covering options (2E-VRP-CO). This problem arises in sustainable applications for e-commerce and city distribution. In the first echelon, trucks depart from a single depot and transport goods to two types of locations. At covering locations, such as parcel lockers, customers can pick up goods themselves. At satellite locations, goods are transferred to zero-emission vehicles (such as cargo bikes) that deliver to customers. If desired, customers can indicate their choice for delivery. The 2E-VRP-CO aims at finding cost-minimizing solutions by selecting locations and routes to serve all customers. We present a compact mixed integer programming formulation and an efficient and tailored adaptive large neighborhood search heuristic that provides high-quality, and often optimal, solutions to the 2E-VRP-CO. The 2E-VRP-CO has as special cases the two-echelon vehicle routing problem, and the simultaneous facility location and vehicle routing problem without duration constraints. On these special cases, for which our heuristic predominantly solves the established benchmark instances either to optimality or to the best-known solution, our heuristic finds three new best-known solutions. Moreover, we introduce a new set of benchmark instances for the 2E-VRP-CO and provide managerial insights when distribution via both satellite and covering locations is most beneficial. Our results indicate that customers in the same area are best-served either via cargo-bikes or parcel lockers (i.e., not both), and that the use of parcel lockers has a great potential to reduce driving distance.

The Fuel Replenishment Problem (FRP) is a multi-compartment, multi-trip, split-delivery VRP in which tanker trucks transport different types of petrol, separated over multiple vehicle compartments, from an oil depot to petrol stations. Large customer demands often necessitate multiple deliveries. Throughout a single working day, a tanker truck returns several times to the oil depot to resupply. A solution to the FRP involves computing a delivery schedule of minimum duration, thereby determining for each vehicle (1) the allocation of oil products to vehicle compartments, (2) the delivery routes, and (3) the delivery patterns. To solve FRP efficiently, an Adaptive Large Neighborhood Search (ALNS) heuristic is constructed. The heuristic is evaluated on data from a Chinese petroleum transportation company and compared against exact results from a MILP model and lower bounds from a column generation approach. In addition, we perform sensitivity analysis on different problem features, including the number of vehicles, products, vehicle compartments and their capacities. Computational results show that the ALNS heuristic is capable of solving instances with up to 60 customers and 3 different products in less than 25 minutes with an average optimality gap of around 10%. On smaller instances, the heuristic finds optimal solutions in significantly less time than the exact MILP formulation.

The determination of critical facilities in supply chain networks has been attracting the interest of the Operations Research community. Critical facilities refer to structures including bridges, railways, train/metro stations, medical facilities, roads, warehouses, and power stations among others, which are vital to the functioning of the network. In this study we address a trilevel optimization problem for the protection of depots of utmost importance in a routing network against an intelligent adversary. We formulate the problem as a defender-attacker-defender game and refer to it as the trilevel r-interdiction selective multi-depot vehicle routing problem (3LRI-SMDVRP). The defender is the decision maker in the upper level problem (ULP) who picks u depots to protect among m existing ones. In the middle level problem (MLP), the attacker destroys r depots among the (m–u) unprotected ones to bring about the biggest disruption. Finally, in the lower level problem (LLP), the decision maker is again the defender who optimizes the vehicle routes and thereby selects which customers to visit and serve in the wake of the attack. All three levels have an identical objective function which is comprised of three components. (i) Operating or acquisition cost of the vehicles. (ii) Traveling cost incurred by the vehicles. (iii) Outsourcing cost due to unvisited customers. The defender aspires to minimize this objective function while the attacker tries to maximize it. As a solution approach to this trilevel discrete optimization problem, we resort to a smart exhaustive enumeration in the ULP and MLP. For the LLP we design a metaheuristic algorithm that hybridizes Variable Neighborhood Descent and Tabu Search techniques adapted to the Selective MDVRP (SMDVRP). The performance of this algorithm is demonstrated on 33 MDVRP benchmark instances existing in the literature and 41 SMDVRP instances generated from them. Numerical experiments on a large number of 3LRI-SMDVRP instances attest that our comprehensive method is effective in dealing with the defender-attacker-defender game on multi-depot routing networks., NA

A way to solve bi-objective problems is to use an effective single objective algorithm embedded inside an e -constraint approach. In this paper, we are interested in any Bi-Objective Vehicle Routing Problem such that if one objective is constrained, the resulting single objective optimization problem can be solved by a state-of-the-art column generation-based method. We propose mechanisms and techniques to significantly speed up the resulting algorithm. Computational experiments are conducted on two problems: the Bi-Objective Vehicle Routing Problem With Time Windows and the Bi-Objective Team Orienteering Problem with Time Windows. To the best of our knowledge, this paper presents the first exact method proposed for the first problem and the second exact method proposed for the second problem. On the first problem we demonstrate the effectiveness of the proposed mechanisms. On the second problem, our algorithm is competitive with algorithms from the literature.

Cross-docking is a strategy to facilitate a persistent process from suppliers to the consumer points, without long-term storage of products at a distribution warehouse. Products are collected from various origins by inbound trucks, unloaded to the cross-dock, reconsolidated with other products, and finally loaded onto outbound trucks within the same or next day. Because of the limited number of dock-doors as the main resources and the uncertain arrival time of trucks at the cross-dock, queue problems in such environments are unavoidable. This study considers a vehicle routing problem (VRP) for a multi-door cross-docking system with a queuing approach. A real application of the proposed model can be found in congestion conditions at the cross-docking yard, when the queuing time of the vehicles (i.e., the queuing delay) may reduce the quality of service. Moreover, in some cases, improper queue management at a facility such as a cross-dock may incur an economic cost associated with the waiting time in the queue. In this study, we focus on the receiving doors of a cross-dock and assume that the rate of truck arrivals at the cross-dock is a random variable. Moreover, the cross-dock is not able to provide service to all vehicles simultaneously; it has some limitations such as capacity constraints and service time restrictions. Thus, an M/M/c queuing formulation is proposed to model this cross-docking environment, in which the vehicles’ dispatch plan for starting the pickup process would also be determined. In the proposed multi-channel queuing system, the arrival flow of trucks to the cross-docking terminal can be deemed as a Poisson process, resulting in a nonlinear mathematical formulation to optimize the problem. The model is then linearized. To handle its computational complexity, we develop a new Genetic Algorithm (GA) to obtain near-optimal solutions to the problem and compare them with those of the optimization software GAMS. Then, a sensitivity analysis is done on different parameters of the model, and their effect on transportation cost and waiting cost of vehicles in the queue is investigated. The results show that considering a queuing approach in this problem, even for a small-scale problem derived from a real case study, can improve the average waiting time of trucks in the queue considerably compared with the situation in which all parameters are assumed deterministic.

A new “rich” variation on the multi-objective vehicle routing problem (VRP), called the multi-tiered vehicle routing problem with global cross-docking (MTVRPGC), is introduced in this paper. With respect to previously studied VRPs, the MVRPTGC includes the following novel features: (i) segregation of facilities into different tiers that distinguish them in terms of different processing and storage capabilities, (ii) cross-docking at a pre-specified subset of facilities in the network (a feature referred to as global cross-docking), and (iii) the possibility of spill-over into subsequent planning periods of demand for facility visitation. The problem originated from a real-life application concerning the collection and delivery of pathology specimens in the transportation network of a pathology health-care service provider. Other industrial applications may, however, benefit from this type of VRP, such as mail sorting. A mixed integer linear programming (MILP) model for this VRP is proposed, and tested computationally in respect of seventeen small hypothetical test instances. A multi-objective ant colony optimisation (MACO) algorithm for solving larger real-world instances of the MTVRPGC is also proposed. The solutions returned by the MACO algorithm are compared with those achieved by the MILP in respect to sixteen instances and also compared to actual collection and delivery routes of a real pathology healthcare service provider operating in South Africa and it is found that adopting the routes suggested by the algorithm results in substantial improvements of all the objectives pursued relative to the status quo.

We consider the problem of designing vehicle routes in a distribution system that are at the same time cost-effective and visually attractive. In this paper we argue that clustering, a popular data mining task, provides a good proxy for visual attractiveness. Our claim is supported by the proposal of a bi-objective capacitated vehicle routing problem in which, in addition to seek for traveling cost minimization, optimizes clustering criteria defined over the customers partitioned in the different routes. The model is solved by a multi-objective evolutionary algorithm to approximate its Pareto frontier. We show, by means of computational experiments, that our model is able to characterize vehicle routing solutions with low routing costs which are, at the same time, attractive according to the visual metrics proposed in the literature.

Asset localization represents an important application over wireless sensor networks (WSN) with a wide area of applicability ranging from network surveillance to search and rescue operations. In this paper, we address a research problem of network management where resource constrained sensors, in terms of capacity, sensing range and energy, are assigned to multiple targets in order to optimally localize assets with minimized error. We consider a heterogeneous network of omnidirectional sensors, each of which has an individual capacity to focus on a number of targets and a specific range to accurately estimate its distances to the targets that it is focusing on. A proper localization of each target requires a minimum of K (typically three) sensors where the target location is estimated using the intersection of the K range circles. We further analyze the problem under the constraint of a globally specified overall WSN energy budget which limits the possible assignments for the capacitated sensors. Restricting the energy budget leads to a trade-off between energy conservation and localization performance. In this context, we propose a heuristic solution approach leveraging evolutionary learning followed by meta-heuristic improvements based on target swapping among sensors. This approach actually minimizes a quantifier that is composed of the total localization area for all targets in addition to a penalty for each target if it is assigned less than minimum sensors. We provide an illustrative case study for the proposed approach and assess its effectiveness experimentally via benchmark results obtained on a data-set derived from known vehicle routing problem instances.

In the restricted planar location problems, facilities cannot be located inside certain areas on the plane. We define congested regions as polygonal areas on the plane inside which locating a facility is infeasible but through which traveling is possible at an additional fixed cost. The location problem with congested regions on the Euclidean plane is shown to be a generalization of the two most studied problems in the literature, i.e. the restricted planar facility location problems with forbidden regions and with barriers. We propose three metaheuristic algorithms enhanced with a local search procedure to solve the restricted planar location problem. A user interface module is also developed to implement the algorithms on the test instances and analyze computational experiments. The test problem instances include those from the restricted planar facility location literature as well as modified large TSP and VRP instances from the routing literature. The presented computational results show the performance of the proposed algorithms and their effectiveness on solving problems with large size.

The asset protection problem is encountered where an uncontrollable fire is sweeping across a landscape comprising important infrastructure assets. Protective activities by teams of firefighters can reduce the risk of losing a particular asset. These activities must be performed during a time-window for each asset determined by the progression of the fire. The nature of some assets is such that they require the simultaneous presence of more than one fire vehicle and its capabilities must meet the requirements of each asset visited. The objective is then to maximise the value of the assets protected subject to constraints on the number and type of fire trucks available. The solution times to this problem using commercial solvers preclude their use for operational purposes. In this work we develop an Adaptive Large Neighbourhood Search algorithm (ALNS) based on problem-specific attributes. Several removal and insertion heuristics, including some new algorithms, are applied. A new benchmark set is generated by considering the problem attributes. In tests with small instances the ALNS is shown to achieve optimal, or near optimal, results in a fraction of the time required by CPLEX. In a second set of experiments comprising larger instances the ALNS was able to produce solutions in times suitable for operational purposes. These solutions mean that significantly more assets can be protected than would be the case otherwise.

Due to an increase in customer-oriented service strategies designed to meet more complex and exacting customer requirements, meeting a scheduled time window has become an important part of designing vehicle routes for logistics activities. However, practically, the uncertainty in travel times and customer demand often means vehicles miss these time windows, increasing service costs and decreasing customer satisfaction. In an effort to find a solution that meets the needs of real-world logistics, we examine the vehicle routing problem with hard time windows under demand and travel time uncertainty. To address the problem, we build a robust optimization model based on novel route-dependent uncertainty sets. However, due to the complex nature of the problem, the robust model is only able to tackle small-sized instances using standard solvers. Therefore, to tackle large instances, we design a two-stage algorithm based on a modified adaptive variable neighborhood search heuristic. The first stage of the algorithm minimizes the total number of vehicle routes, while the second stage minimizes the total travel distance. Extensive computational experiments are conducted with modified versions of Solomon’s benchmark instances. The numerical results show that the proposed two-stage algorithm is able to find optimal solutions for small-sized instances and good-quality robust solutions for large-sized instances with little increase to the total travel distance and/or the number of vehicles used. A detailed analysis of the results also reveals several managerial insights for decision-makers in the logistics industry.

In upstream offshore petroleum logistics, periodic supply vessel planning plays an important role since it ensures the replenishment of offshore installations on a regular basis with all the necessary equipment and materials from an onshore base. The problem involves the determination of the fleet composition and of the vessel schedules over a given time horizon. We present an extended version of this problem involving flexible departures from the base and the possibility of coupling vessels by swapping their schedules. We propose a voyage-based model that can be solved exactly for small- and medium-size instances. For the solution of larger instances, we have developed an adaptive large neighborhood heuristic, which yields optimal or near-optimal solutions relatively fast on small- and medium- size instances. Its performance on larger instances is significantly better than that of alternative algorithms previously developed for the same problem.

In the vehicle routing literature it is generally assumed that each vehicle is driven by a single driver from the beginning to the end of its route. We introduce a new vehicle routing problem without this assumption. We consider a problem with two depots in which vehicles must departure from one depot and arrive to the other, while drivers should leave and return to the same depot and their routes can not exceed a given duration. Under these conditions, changes of vehicle are mandatory for the drivers in order to go back to their base depots. These changes can only take place at some particular nodes. Moreover, vehicles and drivers must be synchronized. We model the problem as a vehicle routing problem with two depots and two types of routes, one for drivers and the other for vehicles. We propose a mixed integer programming formulation for the problem and design a branch-and-cut algorithm to solve it. Computational results show that the proposed approach can find optimal solutions for instances with up to 30 nodes.

This paper considers an extension of the vehicle routing problem with time windows, where the arrival of two vehicles at different customer locations must be synchronized. That is, one vehicle has to deliver some product to a customer, like a home theater system, while the crew on another vehicle must install it. This type of problem is often encountered in practice and is very challenging due to the interdependency among the vehicle routes, but has received little attention in the literature. A constraint programming-based adaptive large neighborhood search is proposed to solve this problem. The search abilities of the large neighborhood search and the constraint propagation abilities of constraint programming are combined to determine the feasibility of any proposed modification to the current solution. Numerical results are reported on instances derived from benchmark instances for the vehicle routing problem with time windows with up to 200 customers.

In the Vehicle Routing Problem with Backhauls (VRPB), the customer set is partitioned into linehaul customers who require deliveries, and backhaul customers who require pickups. Both the linehaul customers and the backhaul customers must be visited contiguously, and all routes must contain at least one linehaul customer. All deliveries have to be loaded at the depot, and all pickups up have to be transported to the depot. This survey paper aims to comprehensively review the existing literature on VRPBs, including models, exact and heuristic algorithms, variants, industrial applications and case studies, with an emphasis on the recent literature. The paper contains several synthetic tables and proposes a number of promising research directions.

In this paper, we consider a special case of vehicle routing problem that addresses the routing problem in a semiconductor supply chain. This paper proposes two Mixed Integer Linear Programming (MILP) models for solving the Green Vehicle Routing Problems with Pickups and Deliveries in a Semiconductor Supply Chain (G-VRPPD-SSC). The first MILP model considers the basic G-VRPPD-SSC problem, and the objective is to find the set of minimum cost routes and schedules for the alternative fuel vehicles in order to satisfy a set of requests which comprise pickup and delivery operations, without violating the product and vehicle compatibility, vehicle capacity, request-priorities and request-types, and start/completion time constraints. The second model extends the first model in order to handle the scenario of having different fuel prices at different refueling stations, and the objective is to minimize the sum of costs of operating alternative fuel vehicles, which include both the routing cost and the refueling cost. To relatively evaluate the performance of the proposed MILP models, we consider the Pickup and Delivery Problem in a Semiconductor Supply Chain (PDP-SSC) without the presence of alternative fuel vehicles, and we present the corresponding MILP model. Our model is compared with an MILP model present in the literature. Our study indicates that the proposed model for the PDP-SSC gives better lower bounds than that by the existing work, apart from performing better than the existing work in terms of requiring less CPU time. In all cases, the proposed three MILP models preform quite good in terms of the execution time to solve the generated problem instances.

Multi-objective (MO) optimization, i.e., the simultaneous optimization of multiple conflicting objectives, is gaining more and more attention in various research areas, such as evolutionary computation, machine learning (e.g., (hyper-)parameter optimization), or logistics (e.g., vehicle routing). Many works in this domain mention the structural problem property of multimodality as a challenge from two classical perspectives: (1) finding all globally optimal solution sets, and (2) avoiding to get trapped in local optima. Interestingly, these streams seem to transfer many traditional concepts of single-objective (SO) optimization into claims, assumptions, or even terminology regarding the MO domain, but mostly neglect the understanding of the structural properties as well as the algorithmic search behavior on a problem’s landscape. However, some recent works counteract this trend, by investigating the fundamentals and characteristics of MO problems using new visualization techniques and gaining surprising insights. Using these visual insights, this work proposes a step towards a unified terminology to capture multimodality and locality in a broader way than it is usually done. This enables us to investigate current research activities in multimodal continuous MO optimization and to highlight new implications and promising research directions for the design of benchmark suites, the discovery of MO landscape features, the development of new MO (or even SO) optimization algorithms, and performance indicators. For all these topics, we provide a review of ideas and methods but also an outlook on future challenges, research potential and perspectives that result from recent developments.

Vehicle routing problems have drawn researchers’ attention for more than fifty years. Most approaches found in the literature are based on the key assumption that for each pair of points of interest (e.g., customers, depot...), the best origin-destination path can be computed. Thus, the problem can be addressed via a simple graph representation, where nodes represent points of interest and arcs represent the best paths. Yet, in practice, it is common that several attributes are defined on road segments. Consequently, alternative paths presenting different trade-offs exist between points of interest. In this study, we investigate in depth a special representation of the road network proposed in the literature and called a multigraph. This representation enables one to maintain all these alternative paths in the solution space. We present an empirical analyses based on the Vehicle Routing Problem with Time Windows, as a test bed problem, solved with branch-and-price algorithms developed for the different types of graphs. Computational experiments on modified benchmarks from the literature and on instances derived from real data evaluate the impact of the modeling on solution quality.

This paper presents an integrated cross-dock door assignment and vehicle routing problem arising in the operation of cross-dock terminals. It consists of assigning origins to inbound doors, transferring commodities between doors, and routing vehicles from outbound doors to destinations. The objective is to jointly minimize the total material handling and transportation costs. Two formulations of the problem are presented and computationally compared. In addition, we develop a column generation algorithm based on the most promising formulation and a heuristic to obtain lower and upper bounds for the optimal solution of the problem, respectively. Numerical results on a set of benchmark instances with up to 20 origins and 50 destinations confirm the efficiency of the proposed solution algorithms.

This paper addresses a Green Time Dependent Capacitated Vehicle Routing Problem that accounts for transportation emissions. The problem has been formulated and solved using Dynamic Programming approach. The applicability of Dynamic Programming in large sized problems is, however, limited due to exponential memory and computation time requirements. Therefore, we propose a generic heuristic approach, Simulation Based Restricted Dynamic Programming, based on weighted random sampling, the classical Restricted Dynamic Programming heuristic and simulation for the model to solve large sized instances. These decision support tools can be used to aid logistics decision-making processes in urban distribution planning. The added values of the proposed model and the heuristic have been shown based on a real life urban distribution planning problem between a pharmaceutical warehouse and a set of pharmacies, and ten relatively larger instances. The results of the numerical experiments show that the Simulation Based Restricted Dynamic Programming heuristic can provide promising results within relatively short computation times compared to the classical Restricted Dynamic Programming for the Green Time Dependent Capacitated Vehicle Routing Problem. The Simulation Based Restricted Dynamic Programming algorithm yields 2.3% lower costs within 93.1% shorter computation times on average, compared to the classical Restricted Dynamic Programming. Moreover, the analyses on the effect of traffic congestion in our base case reveal that 2.3% benefit on total emissions and 0.9% benefit on total routing cost could be obtained if vehicles start delivery after heavy congested period is passed.

This paper presents the Full Truckload Pickup and Delivery Problem with Resource Synchronization (FT-PDP-RS). It consists of optimizing the transport of materials between sites, using a heterogeneous fleet of trucks, in the context of public works. Full truckload pickup and delivery requests have to be served within time windows. Trucks are synchronized on pickup or delivery locations based on unitary loading and unloading resources. We propose an Adaptive Large Neighborhood Search (ALNS) to solve this problem. Custom destroy and repair operators and an efficient feasibility insertion procedure have been designed to solve it. The method has been evaluated on real instances from the literature and on real case instances from a public works company. Computational experiments confirm the efficiency of the method.

Introduce a new time-dependent UAV heterogeneous fleet routing problem.Consider several objective functions and respect drones operational requirements.Design a MILP model in order to find sets of non-dominated solutions.Consider a model able to tackle multi-layer scenarios with package exchanging points.Integrate UAV into the new concepts of mini/microgrid systems inside smart cities. This paper introduces an Unmanned Aerial Vehicle (UAV) heterogeneous fleet routing problem, dealing with vehicles limited autonomy by considering multiple charging stations and respecting operational requirements. A green routing problem is designed for overcoming difficulties that exist as a result of limited vehicle driving range. Due to the large amount of drones emerging in the society, UAVs use and efficiency should be optimized. In particular, these kinds of vehicles have been recently used for delivering and collecting products. Here, we design a new real-time routing problem, in which different types of drones can collect and deliver packages. These aerial vehicles are able to collect more than one deliverable at the same time if it fits their maximum capacity. Inspired by a multi-criteria view of real systems, seven different objective functions are considered and sought to be minimized using a Mixed-Integer Linear Programming (MILP) model solved by a matheuristic algorithm. The latter filters the non-dominated solutions from the pool of solutions found in the branch-and-bound optimization tree, using a black-box dynamic search algorithm. A case of study, considering a bi-layer scenario, is presented in order to validate the proposal, which showed to be able to provide good quality solutions for supporting decision making.

The well-known multi-vehicle covering tour problem (m-CTP) involves finding a minimum-length set of vehicle routes passing through a subset of vertices, subject to constraints on the length of each route and the number of vertices that it contains, such that each vertex not included in any route is covered. Here, a vertex is considered as covered if it lies within a given distance of at least a vertex of a route. This article introduces a generalized variant of the m-CTP that we called the multi-vehicle multi-covering Tour Problem (mm-CTP). In the mm-CTP, a vertex must be covered at least not only once but several times. Three variants of the problem are considered. The binary mm-CTP where a vertex is visited at most once, the mm-CTP without overnight where revisiting a vertex is allowed only after passing through another vertex and the mm-CTP with overnight where revisiting a vertex is permitted without any restrictions. We first propose graph transformations to convert the last two variants into the binary one and focus mostly on solving this variant. A special case of the problem is then formulated as an integer linear program and a branch-and-cut algorithm is developed. We also develop a Genetic Algorithm (GA) that provides high-quality solutions for the problem. Extensive computational results on the new problem mm-CTP as well as its other special cases show the performance of our methods. In particular, our GA outperforms the current best metaheuristics proposed for a wide class of CTP problems.

This paper studies the Aquaculture Service Vessel Routing Problem (ASVRP), which is an important planning problem arising in sea-based fish farming. In the ASVRP, there is a set of fish farms located in the sea, where each fish farm has one or more service tasks to be performed by a given heterogeneous fleet of service vessels with different capabilities. Some service tasks require simultaneous operation of more than one vessel and might also have time windows and precedence requirements. Furthermore, varying weather conditions make the sailing times and the service times of the tasks time dependent. The objective of the ASVRP is to maximize the value of the service tasks performed within a given planning horizon. We propose a time discrete optimization model for the ASVRP, formulated as a time dependent, prize collecting vehicle routing problem with synchronization constraints and time windows. Furthermore, we present an Adaptive Large Neighborhood Search (ALNS) heuristic for solving the problem. Results on a number of test instances based on real world data show that both the ALNS heuristic and a commercial solver are able to find high quality solutions for small problem instances, while the ALNS heuristic is superior when the problem size increases.

The vehicle routing problem with an incompatible loading constraint and splitting deliveries by order is an extension of the well-known capacitated vehicle routing problem. Some orders cannot be transported alongside others due to some type of products in them or their special requirements on transportation condition. Additionally, splitting delivery by order is an effective method for enhancing vehicle efficiency since a customer might have many orders, and order is a set of compatible products. However, split delivery inevitably creates order receipt complexities and contributes to the significant complications of the problem in terms of formulating not only the model, but also the solution method. This study examines an innovative vehicle routing problem characterized by splitting deliveries by order, and addresses the inconvenience of order receipts and incompatibility among orders when fulfilling practical logistics requirements. We formulate this problem as an integer programming model, and the goal is to minimize the sum of routing cost and receipt cost. Then, two hybrid heuristic algorithms called MCWS-LS and S-ALNS are proposed to solve this problem. Furthermore, we conduct a series of experiments over existing vehicle routing problem instances, as well as analyze them under a realistic background to evaluate and demonstrate the effectiveness of the proposed model and algorithms.

The rapid growth of e-commerce has led to an increase of home delivery requests. Providing efficient distribution systems for services on the last mile has become a challenging issue for logistics companies, where a trade-off between the classical approaches, attended home delivery (AHD) and usage of shared delivery locations (SDLs) has been identified. AHD provides a higher quality of service but implies very high costs for the company, while usage of SDL requires customers to perform the very last mile by themselves. For companies, this bears the risk of a decrease in the perceived service quality. However, due to consolidation effects, transportation costs can be considerably mitigated. We propose a mixed delivery approach, which combines AHD and SDL usage in an innovative way. Customers can either be served at home during their preferred time window, or they can be asked to pick up their parcel at one of the SDLs. For each customer served using an SDL, the company pays a compensation price in order to reduce the perceived decrease in service quality. The newly introduced decision problem is formulated mathematically. We propose two matheuristics to efficiently solve large instances. In an extensive numerical study, we show that the new approach clearly outperforms standard ones. We observe an increase in solution quality of up to 40%, while customers’ perceived quality of service is not affected. Additionally, the results reveal that the obtained improvements are robust for different customer-specific time-window preferences, accepted travel times needed to reach an SDL, and different compensation schemes.

We consider logistic collaborations where multiple carriers collaborate by consolidating demands, combining delivery routes, and serving new customers. Logistic collaborations are known to provide numerous benefits such as an increase in profit as well as a reduction in emissions for all parties involved. One of the challenges associated with collaborations is the allocation of the additional profits. To this end, we model the corresponding profit allocation problem as a collaborative game. Here, the profit obtained by any subset of the collaborating carriers depends on the new customers served by the remaining carriers. Specifically, we try to determine an allocation in the core based on both the best-case profit and the worst-case profit that each subset of carriers can attain. To achieve this, we propose a heuristic row generation algorithm. We verify the performance of this algorithm on instances derived from benchmark instances of the capacitated vehicle routing problem. We show that our heuristic algorithm scales well with respect to the number of carriers considered and provides allocations similar to those obtained by enumerating all best-case and worst-case profits of each coalition.

Quantum Annealing was previously applied to the vehicle routing problem and the results were promising. For all benchmark instances in the study, optimal results were obtained. However, 100% success rate was not achieved in every case, and tuning the control parameters for larger instances proved cumbersome. This work addresses these remaining difficulties. An empirical approach is taken wherein measurements of run-time behaviour are exploited to transform existing good values of control parameters so that they can be used successfully for other problem instances. The course of this work shows a method which simplifies hand-tuning so that the heuristic performs successfully when applied to larger instances, and also demonstrates a tuning method which establishes control parameter values for instances which belong in broadly defined groupings. In addition, new best known solutions for large-scale instances, and initial results for the distance-constrained variant of the vehicle routing problem are presented.