Publications

The drone delivery problem (DDP) has been introduced to include aerial vehicles in last-mile delivery operations to increase efficiency. However, the existing studies have not incorporated the communication quality requirements of such a delivery operation. This study introduces the communication-aware DDP (C-DDP), which incorporates handover and outage constraints into the conventional multi-depot multi-trip green vehicle routing problem with time windows. In particular, any trip of a drone to deliver a customer package must require less than a certain number of handover operations and cannot exceed a predefined outage duration threshold. A mixed integer programming (MIP) model is developed to minimize the total flight distance while satisfying communication constraints. We present a genetic algorithm (GA) that can solve large instances and compare its performance with an off-the-shelf MIP solver. Computational study shows that the GA and MIP solver performances are equivalent to solving smaller instances. We also compare the GA performance against another evolutionary algorithm, particle swarm optimization (PSO), for larger instances and find that the GA outperforms the PSO with slightly longer CPU times. The results indicate that ignoring the communication constraints would cause significant operational disruption risk and this risk can be easily mitigated with a slight sacrifice from flight distances by incorporating the proposed communication constraints. In particular, the communication performance can be improved by up to 28.9% when the flight distance is increased by 19.1% at most on average.

This paper studies the multi-period home healthcare routing and scheduling problem with homogeneous electric vehicles and time windows. The problem aims to construct the weekly routes of healthcare nurses, which provide service to the patients located at a scattered geographic area. Some patients may require to be visited more than once in the same workday and/or in the same workweek. We consider three charging technologies; normal, fast, and super-fast. The vehicles might be charged during the working day at a charging station or at the end of the working day at the depot. Charging a vehicle at a depot at the end of a working day requires the transfer of the corresponding nurse from the depot to her/his home. The objective is to minimize the total cost that comprises the fixed cost of utilizing healthcare nurses, the energy charging costs, the costs associated with depot-to-nurse home transfer services, and the costs of a patient left unserved. We formulate a mathematical model and develop an adaptive large neighborhood search metaheuristic that has been efficiently crafted to handle specific problem features. We conduct extensive computational experiments on benchmark instances to assess the competitiveness of the heuristic and to deeply analyze the problem. Our analysis shows the importance of competency level matching as mismatching competency levels could increase the costs of home healthcare providers.

This paper addresses a closed-loop inventory routing problem with demand uncertainty, which manages the delivery operations to customers and pick-up operations of empty returnable transport items (RTIs) from customers. The problem involves decisions regarding forward and backward vehicle routes, the delivery and collection quantities, the amount of production in terms of the number of filled RTIs, and the number of RTIs produced/ bought by the vendor during the defined planning horizon. The problem considers the holding costs, fixed cost of operating vehicles, fuel consumption cost, producing/buying costs, cleaning costs of RTIs, and loading and unloading costs. We formulate the problem as a mixed integer linear programming model and propose a Relax and Fix based solution approach to solve large instances. We conduct extensive analyses on a case study derived from a fruit and vegetable distribution network and several hypothetical instances. Our analyses investigate the effects of several problem parameter changes (i.e., average collection rate, customer service level, cost of buying crate and handling cost) on the total logistics cost. Additional numerical analyses are performed to demonstrate the usage of the model for evaluating the cost of being more green and environmental-friendly. Moreover, experiments on relatively large-scaled problems allow us to demonstrate the potential benefits of the proposed heuristic.

This paper addresses a dynamic traveling salesman problem with electric vehicles under stochastic battery depletion. In the problem, traffic density and battery consumption rate are not known precisely, and their probability distributions are subject to change during the transportation operations. The problem has been formulated and solved using the Dynamic Programming (DP) approach. We develop a DP-based heuristic, which combines Restricted DP and Prim’s algorithms, to solve larger instances. The provided algorithms can determine distribution plans that reduce energy consumption and range anxiety of electric vehicle drivers. The added values of the model and the solution approach have been shown based on a case study and 270 instance-setting pairs that involve relatively larger problems. The heuristic algorithm outperformed a benchmark heuristic by providing 6.87% lower calculated required energy on average. The provided decision support tools can be used to assure energy conservation and emission reduction for short-haul freight distribution systems.

This paper studies a joint multi-depot home health care and dialysis problem of routing and scheduling decisions of health specialists. The fleet consists of electric vehicles, which use both public and private charging stations. We formulate the problem as a mixed integer linear programming model. We describe a hybrid adaptive large neighborhood search (ALNS) algorithm, which integrates construction heuristic to generate initial solution and local search procedure based on variable neighborhood descent. The hybrid ALNS successfully combines existing heuristic mechanisms and introduces several new problem-specific procedures to effectively handle the complex structure of the problem. We conduct experiments on realistic benchmark instances to investigate various problem specifications, such as constructed teams, usage rate of fast and super-fast charging technologies, and public and private charging options. We analyze the performance of the hybrid ALNS and its mechanisms. The algorithm obtained good quality results on the complex optimization problem.

We introduce the Mixed Fleet Vehicle Routing Problem with Time Windows and Partial Recharging by Multiple Chargers (MF-VRP-MC). It composes of electric and internal combustion vehicles, and consolidates several aspects in a comprehensive unique model. The MF-VRP-MC considers travelled distance and carried load on vehicles in both emission and energy consumption functions. It deals with the minimization of total cost while satisfying customer delivery demands. First, we develop a mixed integer mathematical programming formulation for the MF-VRP-MC. Because of the NP-hardness of the problem, to solve medium and large-size instances, then we develop an Adaptive Large Neighborhood Search (ALNS) based algorithm with introducing new advanced neighborhood mechanisms to successfully handle complex problem constraints. Meantime, new approaches are tailored for boosting diversification effect in addition to new neighborhood scoring policy and new enhancement procedure. Furthermore, selection of recharging technology among the others at charging station is firstly considered in the solution phase of a mixed fleet problem. Extensive computational results indicate that our ALNS performs quite well on benchmark instances.

This paper introduces the electric home health care routing and scheduling problem with time windows and fast chargers. The problem aims to construct the daily routes of health care nurses so as to provide a series of services to the patients located at a scattered area. The problem minimizes the total cost, which comprises of total traveling cost of electric vehicles, total cost of uncovered jobs, and total costs of recharged energy. We develop an adaptive large neighborhood search heuristic, which contains a number of advanced efficient procedures tailored to handle specific features of the problem. The paper conducts extensive computational experiments on generated benchmark instances and assesses the competitiveness of the heuristic. Results show that the heuristic is highly effective on the problem. Our analyses quantify the advantages of considering all charger technologies, i.e., normal, fast- and super-fast. We show that the downgrading of competence levels of jobs yields an improvement in total cost.

This paper introduces the Fleet Size and Mix Vehicle Routing Problem with Synchronized Visits (FSM-VRPS), an extension of the Vehicle Routing Problem with Synchronization (VRPS), where a mixed fleet composed of electric and conventional bikes, and passenger cars having different acquisition costs are considered. The problem consists of planning a set of different vehicle routes to serve a set of clients who may require more than one visit by different healthcare specialists, and some of these visits should be synchronized. Moreover, each client must be visited within a specified time window. In addition, the problem uses bikes to reduce Carbon Dioxide (CO2) emission for environmentally cleaner routing operations. This problem has many real-life applications, such as the scheduling of visits for homecare givers in the healthcare sector. We present a mixed integer linear-programming formulation and develop a Multi-Start Adaptive Large Neighborhood Search with Threshold Accepting algorithm. The results showed that our algorithm is highly effective on the FSM-VRPS, as well as on the heterogeneous VRPS. We also demonstrate the advantage of adopting different types of vehicles in terms of reducing the number of vehicles and costs. The analysis of the results also indicated that the new components added to the standard Adaptive Large Neighborhood Search algorithm enhanced intensification and diversification mechanisms during the search process.

This paper introduces the airport shuttle bus scheduling problem (ASBSP) as a new practical scheduling variant. In this problem, a number of identical vehicles that have a specific number of available seats provides transfer service between the airport and the city centre. After making a transfer in one direction, the vehicle can either make a new transfer in the opposite direction depending on the availability and the schedule of the passengers or make an empty return to make a new transfer in the same direction. The vehicles can wait in either location until their next transfer. The passengers have certain time windows for the transfer in relation to their flight times and operational rules to satisfy customer satisfaction. This is a profit-seeking service where transfer requests can also be rejected. The ASBSP aims to prepare a daily schedule for the available vehicles and to assign passengers to these vehicles with the objective of maximising the total profit. This paper presents two alternative mixed integer programming formulations and proposes two valid inequalities to get better bounds. Furthermore, it develops a hybrid metaheuristic that integrates multi-start, simulated annealing and large neighbourhood search for its solution. Extensive computational experiments on real-life benchmark instances have been made to test the performances of the formulations and the hybrid metaheuristic. Furthermore, the impacts of several problem parameters including the number of vehicles, vehicle capacity, transfer fee, transportation time and allowable passenger waiting times on the problem complexity and results have been investigated.

This paper studies the green vehicle routing problem with simultaneous pickup and delivery (G-VRPSPD). It aims to minimize fuel consumption costs while satisfying customer pickup and delivery demands simultaneously. The fuel consumption is directly proportional to green house gas emissions. We mathematically formulate the problem, and develop a hyper-heuristic (HH-ILS) algorithm based on iterative local search and variable neighborhood descent heuristics to effectively solve the problem. Extensive computational experiments are conducted to analyze the impact of the G-VRPSPD and the HH-ILS. We investigate the effect of green objective function on total fuel consumption cost by comparing the G-VRPSPD with the VRPSPD. We perform comparative analysis to investigate the performance of HH-ILS. We also conduct sensitivity analysis to investigate the performance of neighborhood structures, hyper heuristic and local search. The results show that the green objective function has a significant effect on total fuel consumption cost. The HH-ILS algorithm yields competitive results when compared with the mathematical formulation and the state-of-the-art heuristics in the literature.

This paper introduces the integrated disassembly line balancing and routing problem with mobile additive manufacturing (I-DLB-RP-MAM). In the I-DLB-RP-MAM, end-of-life products are first disassembled in a single disassembly center, and a vehicle equipped with a 3D printer then dispatches both recycled and 3D printed components to the customers, i.e. remanufacturing centers. Several demanded components are obtained in disassembly center and the remaining amounts are produced by 3D printer en-route. We formulate a non-linear mathematical programming model for the I-DLB-RP-MAM. We conduct experiments on a numerical example-based on a real product. Scenario analysis is conducted and results show that additive manufacturing technology can be successfully incorporated into the supply chain. We obtain significant improvements such as reduction in inventory and total cost.

This paper introduces the integrated disassembly line balancing and routing problem (I-DLB-RP). The I-DLB-RP simultaneously optimises two well-known problems. The former one balances the disassembly lines in the disassembly centres, whereas the latter one constructs a routing plan to distribute the usable components, generated by the disassembly process, from disassembly centre to the remanufacturing centres, i.e. customers. With the increasing importance of the disassembly process for tackling with the burden of waste and the number of disassembled products, the distribution planning of usable components released after the disassembly process becomes essential. This paper considers several scenarios: single-component distribution, multi-component distribution, inventory cost, and multi-period conditions. We propose five linear and non-linear mathematical models. Extensive computational experiments conducted on generated realistic benchmark instances. The analyses quantify the benefits of integrating the two problems.

In the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), goods have to be transported from different origins to different destinations, and each customer has both a delivery and a pickup demand to be satisfied simultaneously. The VRPSPD has been around for about 30 years, and significant progress has since been made on this problem and its variants. This paper aims to comprehensively review the existing work on the VRPSPD. It surveys mathematical formulations, algorithms, variants, case studies, and industrial applications. It also provides an overview of trends in the literature and identifies several interesting promising future research perspectives.

The road transportation is one of the largest contributors to greenhouse gas emissions globally, and rapid urbanisation increases the environmental and economic challenges. Electric vehicles support green supply chain and clean routing operations when compared with the traditional fossil fuel-powered vehicles. This paper analyses a variant of the home health care routing problem in which a group of health care workers performs a requested number of jobs by using electric vehicles. The problem considers multi-depot, heterogeneous fleet, time windows, preferences, competencies, connected activities, the range of electric vehicles, charging status, and charge strategies. We develop a hybrid metaheuristic which successfully combines genetic algorithm and a variable neighbourhood descent, and offer several algorithmic procedures tailored to handle the rich constraints of the problem. Extensive computational experiments on small, medium and large-scale instances have shown that the hybrid metaheuristic is effective on the problem.

This paper analyses the joint impact of depot location and routing decisions on emissions in freight transportation. We study a variant of the location-routing problem by considering environmental objectives and time windows. The aim is to minimize the sum of depot cost, driver cost, and the cost of fuel and CO2 emissions. The paper develops an adaptive large neighborhood search metaheuristic which was applied to a large pool of benchmark instances and offers a number of advanced procedures. Extensive analyses assess the effect of various problem parameters, such as depot cost, number of potential depots and depot capacity, on key performance indicators. The paper also offers several managerial and policy insights on economies of environmental friendly location-routing.

We introduce the electric vehicle routing problem with shared charging stations (E-VRP-SCS). The E-VRP-SCS extends the electric vehicle routing problem with nonlinear charging function (E-VRP-NL) by considering several companies that jointly invest in charging stations (CSs). The objective is to minimize the sum of the fixed opening cost of CSs and the drivers cost. The problem consists of deciding the location and technology of the CSs and building the routes for each company. It is solved by means of a multistart heuristic that performs an adaptive large neighborhood search coupled with the solution of mixed integer linear programs. It also contains a number of advanced efficient procedures tailored to handle specific components of the E-VRP-SCS. We perform extensive computational experiments on benchmark instances. We assess the competitiveness of the heuristic on the E-VRP-NL and derive 38 new best known solutions. New benchmark results on the E-VRP-SCS are presented, solved, and analyzed.

This paper introduces the Multi-Vehicle Probabilistic Covering Tour Problem (MVPCTP) which extends the Covering Tour Problem (CTP) by incorporating multiple vehicles and probabilistic coverage. As in the CTP, total demand of customers is attracted to the visited facility vertices within the coverage range. The objective function is to maximize the expected customer demand covered. The MVPCTP is first formulated as an integer non-linear programming problem, and then a linearization is proposed, which is strengthened by several sets of valid inequalities. An effective branch-and-cut algorithm is developed in addition to a local search heuristic based on Variable Neighborhood Search to obtain upper bounds. Extensive computational experiments are performed on new benchmark instances adapted from the literature.

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.

This paper introduces the vehicle routing and truck driver scheduling problem with idling options, an extension of the long-haul vehicle routing and truck driver scheduling problem with a more comprehensive objective function that accounts for routing cost, driver cost and idling cost, i.e., the cost associated with energy supply used to maintain drivers’ comfort when the vehicle is not moving. For the idling cost, we consider Electrified Parking Space (EPS) and Auxiliary Power Unit (APU) usage costs. The use of EPSs or APUs avoids keeping the engine running while the vehicle is not moving. We develop a multi-start matheuristic algorithm that combines adaptive large neighborhood search and mixed integer linear programming. We present extensive computational results on instances derived from the Solomon test bed.

This paper investigates the combined impact of assembly line balancing decisions within a supply chain network design. The aim of the problem is to design a supply chain network between manufacturers, assemblers, and customers for specific periods, as well as balancing the assembly lines in assemblers. The main objective is to minimize the sum of transportation costs and fixed costs of stations in assemblers. Solving this problem poses several methodological challenges. To this end, the paper developed a powerful evolutionary algorithm (EA) which was successfully applied to a large pool of benchmark instances. The EA solved instances with up to 140 manufacturers and customers, and with up to 130 assemblers. Computational analyses are performed to empirically calculate the effect of various problem parameters, such as total cost, transportation cost and number of stations. The EA is validated on benchmark instances where it provides competitive solutions. Several managerial insights are also presented.

This paper introduces three variants of the Periodic Location-Routing Problem (PLRP): the Heterogeneous PLRP with Time Windows (HPTW), the Heterogeneous PLRP (HP) and the homogeneous PLRP with Time Windows (PTW). These problems extend the well-known location-routing problem by considering a homogeneous or heterogeneous fleet, multiple periods and time windows. The paper develops a powerful Unified-Adaptive Large Neighborhood Search (U-ALNS) metaheuristic for these problems. The U-ALNS successfully uses existing algorithmic procedures and also offers a number of new advanced efficient procedures capable of handling a multi-period horizon, fleet composition and location decisions. Computational experiments on benchmark instances show that the U-ALNS is highly effective on PLRPs. The U-ALNS outperforms previous methods on a set of standard benchmark instances for the PLRP. We also present new benchmark results for the PLRP, HPTW, HP and PTW.

The process by which olive oil is produced yields two by-products, one of which is the brown-coloured Olive Oil Mill Wastewater (OMWW) and has no direct use. OMWW is generally disposed of into soil or rivers, potentially contaminating the environment. OMWW can be treated using ultrafiltration facilities, but this requires that OMWW is collected from oil mills and delivered to the treatment facilities using a fleet of vehicles in an economically viable manner. Such considerations give rise to a multiperiod location-routing problem. This paper formally introduces the problem and proposes an adaptive large neighbourhood search metaheuristic for its solution. The algorithm is applied on a case study drawn from one of the major olive oil producing countries. The paper presents computational and managerial results.

This paper develops a simulated annealing heuristic based exact solution approach to solve the green vehicle routing problem (G-VRP) which extends the classical vehicle routing problem by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. The problem particularly arises for companies and agencies that employ a fleet of alternative energy powered vehicles on transportation systems for urban areas or for goods distribution. Exact algorithm is based on the branch-and-cut algorithm which combines several valid inequalities derived from the literature to improve lower bounds and introduces a heuristic algorithm based on simulated annealing to obtain upper bounds. Solution approach is evaluated in terms of the number of test instances solved to optimality, bound quality and computation time to reach the best solution of the various test problems. Computational results show that 22 of 40 instances with 20 customers can be solved optimally within reasonable computation time.

This paper studies the Truck Driver Scheduling Problem with Idling Options (TDSP-IO), an extension of the long-haul truck driver scheduling problem with a more comprehensive objective function that accounts for driving cost, fuel cost, and idling cost. The best-known idling option is the widespread practice of keeping the vehicle engine running while the vehicle is not moving, which primarily stems from the drivers’desire to keep their vehicle at an adequate comfort level during breaks. Here, we explore two additional cleaner idling options: resting at an Electrified Parking Space (EPS) or using an Auxiliary Power Unit (APU) while idling. We also account for the initial investments associated with the equipment required for the use of these technologies. We formulate a mathematical model for the TDSP-IO under these three idling options, and we perform extensive computational experiments on realistic benchmark instances. The paper sheds light on the trade-offs between various performance indicators and offers several managerial and policy insights. Our analyses quantify the advantages of using EPSs and APUs, and show that they yield both economical and environmental benefits.

This paper investigates the combined impact of depot location, fleet composition and routing decisions on vehicle emissions in city logistics. We consider a city in which goods need to be delivered from a depot to customers located in nested zones characterized by different speed limits. The objective is to minimize the total depot, vehicle and routing cost, where the latter can be defined with respect to the cost of fuel consumption and CO2 emissions. A new powerful adaptive large neighborhood search metaheuristic is developed and successfully applied to a large pool of new benchmark instances. Extensive analyses are performed to empirically assess the effect of various problem parameters, such as depot cost and location, customer distribution and heterogeneous vehicles on key performance indicators, including fuel consumption, emissions and operational costs. Several managerial insights are presented.

It has been around 30 years since the heterogeneous vehicle routing problem was introduced, and significant progress has since been made on this problem and its variants. The aim of this survey paper is to classify and review the literature on heterogeneous vehicle routing problems. The paper also presents a comparative analysis of the metaheuristic algorithms that have been proposed for these problems.

This paper introduces the fleet size and mix location-routing problem with time windows (FSMLRPTW) which extends the location-routing problem by considering a heterogeneous fleet and time windows. The main objective is to minimize the sum of vehicle fixed cost, depot cost and routing cost. We present mixed integer programming formulations, a family of valid inequalities and we develop a powerful hybrid evolutionary search algorithm (HESA) to solve the problem. The HESA successfully combines several metaheuristics and offers a number of new advanced efficient procedures tailored to handle heterogeneous fleet dimensioning and location decisions. We evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions. We also investigate the performance of the HESA. Extensive computational experiments on new benchmark instances have shown that the HESA is highly effective on the FSMLRPTW.

This paper presents a hybrid evolutionary algorithm (HEA) to solve heterogeneous fleet vehicle routing problems with time windows. There are two main types of such problems, namely the fleet size and mix vehicle routing problem with time windows (F) and the heterogeneous fixed fleet vehicle routing problem with time windows (H), where the latter, in contrast to the former, assumes a limited availability of vehicles. The main objective is to minimize the fixed vehicle cost and the distribution cost, where the latter can be defined with respect to en-route time (T) or distance (D). The proposed unified algorithm is able to solve the four variants of heterogeneous fleet routing problem, called FT, FD, HT and HD, where the last variant is new. The HEA successfully combines several metaheuristics and offers a number of new advanced efficient procedures tailored to handle the heterogeneous fleet dimension. Extensive computational experiments on benchmark instances have shown that the HEA is highly effective on FT, FD and HT. In particular, out of the 360 instances we obtained 75 new best solutions and matched 102 within reasonable computational times. New benchmark results on HD are also presented.

This paper introduces the fleet size and mix pollution-routing problem which extends the pollution-routing problem by considering a heterogeneous vehicle fleet. The main objective is to minimize the sum of vehicle fixed costs and routing cost, where the latter can be defined with respect to the cost of fuel and CO2 emissions, and driver cost. Solving this problem poses several methodological challenges. To this end, we have developed a powerful metaheuristic which was successfully applied to a large pool of realistic benchmark instances. Several analyses were conducted to shed light on the trade-offs between various performance indicators, including capacity utilization, fuel and emissions and costs pertaining to vehicle acquisition, fuel consumption and drivers. The analyses also quantify the benefits of using a heterogeneous fleet over a homogeneous one.