Search

The vehicle routing problem (VRP) is a combinatorial optimization problem faced by transportation services related to pick up or delivery, such as industrial raw materials distribution, tour and travel, or travel routing problems in general. VRP is an NP-hard problem where the higher the dimensions of the problem will have a higher computational complexity. Without realizing it, VRP problem are often encountered every day. Therefore, it will be very useful if VRP solver is implemented in mobile application media. So, the aim of this work is developing a mobile application to get the shortest path and minimal cost in VRP problem. It is integrated by both Mapbox API and Google Maps API to get a real distance for modeling problem. The result show that the developed application can run well in all possibility condition.

This work focuses on the capacitated vehicle routing problem. In this work, a real-time application is developed using online real-world data for mobile devices have IOS and Android operating systems. The fuzzy c-means clustering algorithm is used to group the demand points and the ant colony optimization algorithm is employed to determine the best route within each group. The customer demand points and distances between these points are obtained via Google Places and Google Directions APIs. The deviations in the route that result from the environmental and road conditions are identified immediately with the help of global positioning system technology allowing the route suggestions to be made. The developed application was evaluated on two datasets for testing. The test results showed that this real-time application can be used to find the optimum route for the capacitated vehicle routing problem and follow the route optimally.

Existing deep reinforcement learning (DRL) based methods for solving the capacitated vehicle routing problem (CVRP) intrinsically cope with homogeneous vehicle fleet, in which the fleet is assumed as repetitions of a single vehicle. Hence, their key to construct a solution solely lies in the selection of the next node (customer) to visit excluding the selection of vehicle. However, vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed), rendering existing DRL methods less effective. In this paper, we tackle heterogeneous CVRP (HCVRP), where vehicles are mainly characterized by different capacities. We consider both min-max and min-sum objectives for HCVRP, which aim to minimize the longest or total travel time of the vehicle(s) in the fleet. To solve those problems, we propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step. Experimental results based on randomly generated instances show that, with desirable generalization to various problem sizes, our method outperforms the state-of-the-art DRL method and most of the conventional heuristics, and also delivers competitive performance against the state-of-the-art heuristic method, i.e., SISR. Additionally, the results of extended experiments demonstrate that our method is also able to solve CVRPLib instances with satisfactory performance., Comment: This paper has been accepted at IEEE Transactions on Cybernetics

This paper introduces the Hierarchical Multi-Switch Multi-Echelon Vehicle Routing Problem, a new variant of the well-known Vehicle Routing Problem. It is a real-world problem originating from the policies of a Nordic distribution company. The problem includes a single depot, a non-predetermined hierarchy of intermediate facilities, and two different fleets, consisting of homogeneous original and homogeneous local vehicles, which are pulling swap-bodies. Original vehicles with attached swap-bodies depart from the central depot. They can either visit customers directly if only one swap-body is attached or visit one or two consecutive switch points in order to transfer one or two loaded swap-bodies to a corresponding number of local vehicles, which are subsequently routed to customers while the original vehicle itself proceeds to serve customers with the remaining loaded swap-body. A mixed-integer formulation of the problem is proposed. A short bibliographic review, relations, shared characteristics, and differences of the proposed variant and several known VRP variants are analyzed and discussed. The solution of an illustrative instance is presented in order to demonstrate the solution concept for the problem as well as to compare with solution concepts for previously stated VRP variants. Computational experiments on small instances that could be solved within one hour are also presented. The problem is computationally hard to solve. Thus, the development of heuristics and metaheuristics is an important future task in order to enable solution of real case instances or instances of realistic sizes. Validerad;2023;Nivå 2;2023-06-28 (hanlid);Funder: 2019-2022 Kolarctic CBC Program

We study a shared-storage automated storage and retrieval system (AS/RS) with one crane capable of carrying multiple unit loads. In a shared-storage system, items to be stored are not pre-assigned to dedicated shelf spaces. Therefore, given a set of storage and retrieval requests, the crane scheduling problem consists of deciding which requests are processed together in the same tour, determining the sequence in which the requests are processed, and assigning each storage request to an available slot on the shelf. We reformulate the problem as a special type of capacitated vehicle routing problem, which we use to close some open questions regarding the time complexity of related geometric routing problems. The reformulation allows us to tap into the rich and mature vehicle routing toolbox from the literature to propose a new exact solution approach. We show that this method is capable of solving large instances to optimality, outperforming previous methods from the literature. We use our new approach to derive multiple insights. Specifically, we show that system throughput can be predicted from the capacity of the crane via a simple rule. We also determine the optimal shape of a shelf and investigate the value of having knowledge of multiple requests when planning the crane schedule. Finally, we demonstrate that our approach can easily be extended to solve a whole family of multi-shuttle crane scheduling problems.

Recent technological breakthroughs have allowed unmanned aerial vehicles (UAVs) to be utilized in a broad range of new operations. Among these various applications, herein, we focus on the use of UAVs for search and rescue missions in emergency and postdisaster scenarios. In this context, self-charging technologies for drones create new challenges in the routing of UAVs with charging stations. We present a variant of the vehicle routing problem (VRP) to address the integrated use of UAVs and mobile charging stations and define the VRP with synchronized networks (VRPSN), a new class of VRPs involving the routing of UAVs whose recharge platforms can travel to different locations during an operation. This leads to two networks within the VRP that must be integrated and synchronized. This research develops a mixed-integer linear program model for the VRPSN that considers the use of UAVs and mobile charging stations in a synchronized manner. To overcome the computational limits of the MILP model, this research presents a construct-and-adjust heuristic method integrated with a genetic algorithm. As a numerical example, we test the proposed model on the Corrego do Feijao Mine located in Minas Gerais, Brazil, where a dam recently collapsed, killing many workers. Numerical tests show that the new methodology is an attractive planning method for providing efficient and rapid responses in search and rescue missions.

In this article, we study the reinforcement learning (RL) for vehicle routing problems (VRPs). Recent works have shown that attention-based RL models outperform recurrent neural network-based methods on these problems in terms of both effectiveness and efficiency. However, existing RL models simply aggregate node embeddings to generate the context embedding without taking into account the dynamic network structures, making them incapable of modeling the state transition and action selection dynamics. In this work, we develop a new attention-based RL model that provides enhanced node embeddings via batch normalization reordering and gate aggregation, as well as dynamic-aware context embedding through an attentive aggregation module on multiple relational structures. We conduct experiments on five types of VRPs: 1) travelling salesman problem (TSP); 2) capacitated VRP (CVRP); 3) split delivery VRP (SDVRP); 4) orienteering problem (OP); and 5) prize collecting TSP (PCTSP). The results show that our model not only outperforms the learning-based baselines but also solves the problems much faster than the traditional baselines. In addition, our model shows improved generalizability when being evaluated in large-scale problems, as well as problems with different data distributions.

The development of electric vehicle (EV) techniques has led to a new vehicle routing problem (VRP) called the capacitated EV routing problem (CEVRP). Because of the limited number of charging stations and the limited cruising range of EVs, not only the service order of customers but also the recharging schedules of EVs should be considered. However, solving these two aspects of the problem together is very difficult. To address the above issue, we treat CEVRP as a bilevel optimization problem and propose a novel bilevel ant colony optimization algorithm in this article, which divides CEVRP into two levels of subproblem: 1) capacitated VRP and 2) fixed route vehicle charging problem. For the upper level subproblem, the electricity constraint is ignored and an order-first split-second max-min ant system algorithm is designed to generate routes that fulfill the demands of customers. For the lower level subproblem, a new effective heuristic is designed to decide the charging schedule in the generated routes to satisfy the electricity constraint. The objective values of the resultant solutions are used to update the pheromone information for the ant system algorithm in the upper level. Through good orchestration of the two components, the proposed algorithm can significantly outperform state-of-the-art algorithms on a wide range of benchmark instances.

This article addresses the dynamic vehicle routing problem (DVRP). DVRP is a challenging variation of the classic vehicle routing problem in which some customers are not known in advance. The objective is to incorporate new customers into the schedule as they become known while still attempting to minimize the cost of serving all customers without violating the problem constraints. This work proposes an effective population-based approach that integrates various algorithmic components to address DVRP. The approach combines a local search algorithm with various evolutionary operators (crossover and mutation) in an adaptive manner. To promote diversity, the proposed approach utilizes a population of solutions and uses a quality-and-diversity strategy to retain only promising solutions. The well-known 21 DVRP benchmark instances are utilized to test the performance of the proposed approach. An experimental comparison is carried out to assess the contribution of the integrated components. Results demonstrate that the integrated components significantly improve search performance. It is also shown that the proposed approach produces new best results for several instances when compared with the best methods reported in the literature.

Recent studies in using deep learning to solve routing problems focus on construction heuristics, the solutions of which are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by hand-crafted rules which may limit their performance. In this paper, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention based deep architecture as the policy network to guide the selection of next solution. We apply our method to two important routing problems, i.e. travelling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Experiments show that our method outperforms state-of-the-art deep learning based approaches. The learned policies are more effective than the traditional hand-crafted ones, and can be further enhanced by simple diversifying strategies. Moreover, the policies generalize well to different problem sizes, initial solutions and even real-world dataset., Comment: 10 pages, 4 figures

Congestion recognition is necessary for vehicle routing, traffic control, and many other applications in intelligent transportation systems. Besides, traffic facilities in the three-dimensional road network, which contains the fundamental spatiotemporal features for congestion recognition, provides multi-source traffic information. To exploit these traffic big data, in this paper, we propose an attention mechanism-based digraph convolution network (ADGCN) enabled framework to tackle the congestion recognition problem. It can be divided into two parts, spatial relevance modeling and temporal relevance modeling. At first, the representation incorporates spatiotemporal traffic information with the three-dimensional urban network, and partially decouples the global network topology to a single-knot digraph. Then a digraph-based convolution network is used to capture high-order spatial features. Finally, to proceed with time-series features, the multi-modal attention mechanism is introduced to catch the long-range temporal dependence and the congestion classifier is defined accordingly. This distinguishes the proposed model from the conventional congestion recognition methods. Comprehensive experiments are conducted based on real traffic data. The results demonstrate the advantages of the proposed framework over the existing spatiotemporal analysis methods.

Capacitated Vehicle routing problem is NP-hard scheduling problem in which the main concern is to find the best routes with minimum cost for a number of vehicles serving a number of scattered customers under some vehicle capacity constraint. Due to the complex nature of the capacitated vehicle routing problem, metaheuristic optimization algorithms are widely used for tackling this type of challenge. Coronavirus Herd Immunity Optimizer (CHIO) is a recent metaheuristic population-based algorithm that mimics the COVID-19 herd immunity treatment strategy. In this paper, CHIO is modified for capacitated vehicle routing problem. The modifications for CHIO are accomplished by modifying its operators to preserve the solution feasibility for this type of vehicle routing problems. To evaluate the modified CHIO, two sets of data sets are used: the first data set has ten Synthetic CVRP models while the second is an ABEFMP data set which has 27 instances with different models. Moreover, the results achieved by modified CHIO are compared against the results of other 13 well-regarded algorithms. For the first data set, the modified CHIO is able to gain the same results as the other comparative methods in two out of ten instances and acceptable results in the rest. For the second and the more complicated data sets, the modified CHIO is able to achieve very competitive results and ranked the first for 8 instances out of 27. In a nutshell, the modified CHIO is able to efficiently solve the capacitated vehicle routing problem and can be utilized for other routing problems in the future such as multiple travelling salesman problem.

Background: The aim of this research is to optimize the routing of Brazil nut harvesting in order to reduce labor costs and promote an equitable redistribution of placements among extractive interests. The study area was located in the Tahuamanu province, designated a Biosphere Reserve by UNESCO, in the Madre de Dios region of Peru. Planning for harvesting activities is vital to support sustainable use of the tropical forest by extractive communities, generating profit while minimizing adverse impacts on the forest. A location-allocation model was used to redistribute extraction placement areas, taking into account the number of trees and productivity for analysis. To optimize the order of nut load pickups at the placement areas, the vehicle routing problem (VRP) was used to minimize real distance and reduce traversal time. Results: The time taken to cover the route without delays was 08:46’, which is superior to the time taken to minimize the distance. However, the total delay time was 05:10’. Conclusion: Network analyses were effective in achieving the reallocation of placement areas and optimizing Brazil nut harvest routes.

The National Research Council of Canada (NRC) is committed to supporting the scale ai cluster's goals through its Artificial Intelligence for Logistics program, which includes convener support in supply chain and logistics. The program also provides R&D expertise focused on next-generation technology issues to ensure Canadian excellence in logistics for the longer term. Using its national reach, the NRC program is creating linkages between stakeholders, and enabling the advancement of the technologies and firms that will make supply chain and logistics excellence a competitive advantage for Canada., Le Conseil national de recherches du Canada (CNRC) s'est engagé à appuyer les objectifs de la grappe scale ai par l'entremise de son programme Intelligence artificielle au service de la logistique, reliant des organisations dans les domaines de la chaine d'approvisionnement et de la logistique. Le programme tire parti d'une expertise en R-D axée sur les enjeux technologiques de la prochaine génération afin d'assurer l'excellence de la logistique canadienne à long terme. Fort de sa portée nationale, le programme crée des liens entre les intervenants et permet l'avancement des technologies et des entreprises qui fera de l'excellence dans la gestion de la chaîne d'approvisionnement et de la logistique un avantage concurrentiel pour le Canada.

The vehicle routing problem (VRP) determines preferred vehicle routes to visit multiple customer locations from a depot location based on a defined objective function. The VRP is an NP-hard network optimization problem that is challenging to solve to optimality. Over the past 60 years, multitudes of heuristics and metaheuristics have been developed in order to minimize the computational burden of solving the VRP. In order to compare the performance of VRP heuristics, researchers have developed bench-marking datasets. These datasets, however, lack properties found in industry datasets. In this dissertation, we explore how properties of industry datasets influence VRP heuristics and objective functions. In Chapter 2, we quantify and compare features of bench-marking and industry datasets. In order to determine if these features influence heuristic performance, we conduct extensive computational runs on three heuristics, Tabu Search, Genetic Algorithm, and Clarke-Wright Savings Procedure, on standard and industry datasets. In Chapter 3, we derive worst-case analysis on how VRP objective functions and metrics relate to one another. These bounds depend on properties of customer locations. These bounds illustrate how customer locations can influence how different routes behave for different routing metrics. Finally, in Chapter 4, we improve two VRP heuristics, Clarke-Wright Saving Procedure and Hybrid Genetic Search Algorithm, by developing new enhancements to the algorithms. These enhancements rely on certain properties of the datasets in order to perform well. Thus, these heuristics perform better on specific VRP dataset types. Doctor of Philosophy The vehicle routing problem (VRP) creates vehicle routes that have the shortest travel distance. The routes determine how vehicles should visit multipl customer locations, to deliver or pickup goods, and return to a depot location. While explaining what the VRP entails is simple, the VRP is actually very difficult for even the most sophisticated algorithms on the best computers to solve. Over the past 60 years, many algorithms have been developed in order to more easily and quickly solve the VRP. In order to compare the performance of VRP algorithms, researchers have developed bench-marking datasets. However, these datasets lack properties of datasets found in industry. In this dissertation, we look to connect the disconnect between industry and bench-marking datasets by 1) comparing feature differences between these two types of datasets, 2) determining if differences in datasets imply differences in algorithm performance, 3) proving how problem differences influence VRP routes, and 4) enhancing existing VRP algorithms to perform better on specific VRP dataset types.

Usmjeravanje vozila često je prisutan element mnogih industrija pa tako i morskih luka. Ovaj problem predstavlja ogroman logistički izazov zbog velike količine robe koja se mora prevesti. Kvalitetno rješenje navedenog problema može rezultirati velikom uštedom sredstava. Postoje različiti pristupi rješavanju ovog problema, no i dalje je ovo česta tema istraživanja zbog rastuće složenosti uzrokovane povećanjem industrija. Evolucijski algoritmi igraju veliku ulogu u ovom području jer nude obećavajuće rezultate. Međutim, i dalje ima puno prostora za poboljšanja i istraživanje novih, efektivnijih metoda. Ovaj rad opisuje problem usmjeravanja vozila u morskim lukama i predlaže prikladan evolucijski algoritam koji nastoji kreirati optimalan skup ruta za vozila. Opisana je korištena metoda te analizirani rezultati u usporedbi s relevantnim suvremenim pristupima. Vehicle routing is an often present element of many industries, including seaports. This problem presents a huge logistical challenge due to the large amount of goods that have to be transported. A high-quality solution to the above-mentioned problem can result in a large saving of funds. There are different approaches to solving this problem, but it is still a frequent topic of research due to the growing complexity caused by the increasing demands of industries. Evolutionary algorithms play a major role in this field as they offer promising results. However, there is still a lot of room for improvement and research into new, more effective methods. This paper describes the vehicle routing problem in seaports and proposes a suitable evolutionary algorithm that seeks to create an optimal set of vehicle routes. The method used is described and the results analyzed in comparison with relevant modern approaches.

Every issue we face in daily life can be resolved through mathematical modeling. The use of mathematical modeling to generate solutions frequently produces value that serves a single purpose. Sometimes a single-purpose function's solution does not offer the best solution value. In this study, the author models the multiobjective time-dependent vehicle routing problem using the Ant Colony Optimization (ACO) metaheuristic algorithm. The author then applies the pareto optimization principle to the determination of the optimal starting point for the route. An optimal Pareto frontier principle solution on a multi-objective model under control of the Ant Colony Optimization algorithm is the outcome of this study. &nbsp

The urban population has been growing rapidly, especially in the European Union. The trend of urbanization has led to an increased demand for mobility, through both passenger and goods transportation. One of latest trends in passenger transportation is electric scooters, which have been offered under a framework of shared mobility since 2017. This paper addresses an optimization problem emerging from the process of collecting e-scooters from the streets of Vienna during the night. One of the major planning issues for rental companies is the uncertainty of service times, i.e., the time needed to locate and load the e-scooters onto the vans. We formulated the e-scooter collection problem as an extension of the vehicle routing problem with the goal of minimizing the number of vans needed to collect the scooters and the distance traveled by vans, as well as penalizing belated collection. We proposed a solution method based on a large neighborhood search and solved problem instances generated based on real-world data. We then evaluated the impact of the service time uncertainty on the total system costs through a scenario analysis. Furthermore, we proposed a dynamic re-optimization policy that made use of real-time information on service times. We showed that the dynamic policy outperformed the static policy by 4–17% and could lead to reductions in delays of 49–54%, depending on the standard deviation.

Pandemi Covid-19 yang terjadi di Indonesia pada awal tahun 2020 meng­akibatkan pemberlakuan physical distancing berskala besar sehingga ber­dampak pada meningkatnya permintaan terhadap pengiriman makanan secara online. Dalam usaha meningkatkan pelayanannya dengan jumlah per­mintaan yang meningkat, UMKM rumahan pada penelitian ini merancang rute pengirim­an yang lebih efisien. Pada proses pengiriman sebelumnya hanya berdasarkan kapasitas armada pengiriman dan lokasi pelanggan yang terdekat dengan lokasi UMKM. Penelitian ini bertujuan untuk mengevaluasi rute awal pengirim­an dan menentukan rute baru dan urutan kunjungan ke setiap titik lokasi pe­lang­­gan dengan menggunakan metode saving matrix dan dengan meng­guna­kan algoritma nearest neighbor dan nearest insertion. Dengan mengguna­kan metode saving matrix didapatkan dua rute kunjungan. Ber­dasarkan perban­ding­an hasil pengurutan kunjungan pelanggan pada setiap rute, didapatkan jarak tempuh terpendek dengan menggunakan algoritma nearest neighbor. Total penghematan jarak tempuh yang didapatkan berdasar­kan penentuan rute dengan menggunakan metode saving matrix dan algoritma nearest neighbor adalah sebesar 34.5% (dari total jarak tempuh pada rute awal adalah 77.19 km menjadi 50.59 km pada rute yang baru).

Summarization: This paper presents a Cumulative Unmanned Aerial Vehicle Routing Problem (CUAVRP) approach to optimize Humanitarian Coverage Path Planning (HCPP). Coverage path planning consists of finding the route which covers every point of a certain area of interest. This paper considers a Search & Rescue mission, using a homogeneous fleet of Unmanned Aerial Vehicles (UAVs). In this scenario, the objective is to minimize the sum of arrival times at all points of the area of interest, thus, completing the search with minimum latency. The HCPP problem is transformed into a Vehicle Routing Problem by using an approximate cellular decomposition technique to discretize the area into a grid, where the rectangles represent the UAV sensor’s field of view. The center points of the formed rectangles, become the nodes used for a UAV routing problem. This approach uses the objective of minimizing the sum of arrival times at customers, found in the Cumulative Capacitated Vehicle Routing Problem (CCVRP), adjusted for the Search & Rescue Coverage Path Planning using UAVs. The Min-max objective is also implemented and tested. Three versions of a Parallel Weighted Greedy Randomized Adaptive Search Procedure - Variable Neighborhood Decent (GRASP-VND) algorithm is implemented to solve the Cumulative UAV Routing Problem for Humanitarian Coverage Path Planning. Presented on: European Journal of Operational Research

Cities, retailers, and delivery services are trying to find more environmental friendly solutions for last mile delivery. One very promising and partly used option are cargo bicycles. A critical factor of cargo bicycles is their travel speed, which depends on the mass of the load and the gradient of the chosen streets. Therefore, we define load-dependent travel speed and introduce the vehicle routing problem with load-dependent travel times (VRPLTT). We introduce a mixed-integer programming formulation and show the benefits of considering load-dependent travel times in last mile delivery with cargo bicycles. To efficiently solve larger instances, we develop an adaptive large neighborhood search (ALNS). For the numerical study, we introduce a new set of instances and show that the travel time can be reduced by 4.5% on average and up to 22% compared to the vehicle routing problem with time windows. Moreover, ignoring the load-dependent travel times can lead to the underestimation of travel time in such a way that time windows are violated.

BACKGROUND AND OBJECTIVES: Prior to the COVID-19 pandemic, Hoi An City was one of the most famous tourist destinations in the world. This led to a rapid increase in solid waste generation, leading to problems and challenges in solid waste collection and management. This problem is also being experienced by other developing countries of the world. Despite the existence of established waste management strategies, targets set for the collection of recyclable waste have not been met. This study introduces solutions to the problems and challenges faced by the waste management sector in Hoi An city and other developing countries. This study aimed to i) optimize the map of the recovery recycling stations in an urban community, ii) develop an effective solid waste collection system, and iii) provide management tools to enhance recycling activities, contributing to improving waste management in Hoi An city.METHODS: The RRSs were integrated into a solid waste collection system in the urban communities of Hoi An City, were conducted through location-allocation analysis in a geographic information system environment. Routing problems of carts were solved in the combination of the rescheduling of existing solid waste collection activities in the study site. The economic evaluation by scenarios was also calculated for ten years to assess the feasibility of scenarios.FINDINGS: Thirty-four locations were identified and optimized to accommodate the RRSs and new collection routes. The distances travelled and working time increased in proportion to the increase in waste separation effectiveness. Waste separation is vital to the effectiveness of the new solid waste collection system. The optimal solid waste practice model (in scenarios 2 and 4) revealed the positive results in improving the solid waste collection system, operating economy, and local adaptation.CONCLUSION: This study redesigned the solid waste collection system to solve the current problems in the tourism destination of Hoi An city. This study contributed as a case study of integrating urban recovery recycling stations into optimizing a solid waste collection system in a tourism destination. Introducing strict waste separation was the pivotal first step in systematically upgrading the solid waste collection system in Hoi An City. This study’s findings provide government officials and service providers with methods that can be applied to solve the problems faced by Hoi An city's existing solid waste collection and management system.

After a disaster, often roads are damaged and blocked, hindering accessibility for relief efforts. It is essential to dispatch work teams to restore the blocked roads by clearance or repair operations. With the goal of enabling access between critical locations in the disaster area in shortest time, we propose algorithms that determine the schedule and routes of multiple work teams. We minimize the total latency of reaching the critical locations, where the latency of a location is defined as the time it takes from the start of the operation until its first visit by one of the work teams. Coordination among the teams is needed since some blocked edges might be opened by a certain team and utilized by other teams later on. First, we develop an exact mathematical model that handles the coordination requirement. After observing the intractability of this formulation, we introduce two heuristic methods and a lower bounding procedure. In the first method, we develop a mathematical model based on a novel multi-level network representation that yields solutions with disjoint paths. Given that it does not coordinate the teams, we present a matheuristic based on a cluster-first-route-second approach embedded into a local search algorithm together with an additional coordination step to obtain alternative solutions with higher quality and in a shorter time. We test our heuristics on data sets coming from a real network from the literature (180 instances) and randomly generated ones (640 instances) and observe the superiority of the solutions obtained by incorporation of coordination., NA

The current critical global concerns regarding fossil fuel exhaustion and environmental pollution have been driving advancements in transportation electrification and related battery technologies. In turn, the resultant growing popularity of electric vehicles (EVs) calls for the development of a well-designed charging infrastructure. However, an inappropriate placement of charging stations might hamper smooth operation of the power grid and be inconvenient to EV drivers. Thus, the present work proposes a novel two-stage planning model for charging station placement. The candidate locations for the placement of charging stations are first determined by fuzzy inference considering distance, road traffic, and grid stability. The randomness in road traffic is modelled by applying a Bayesian network (BN). Then, the charging station placement problem is represented in a multi-objective framework with cost, voltage stability reliability power loss (VRP) index, accessibility index, and waiting time as objective functions. A hybrid algorithm combining chicken swarm optimization and the teaching-learning-based optimization (CSO TLBO) algorithm is used to obtain the Pareto front. Further, fuzzy decision making is used to compare the Pareto optimal solutions. The proposed planning model is validated on a superimposed IEEE 33-bus and 25-node test network and on a practical network in Tianjin, China. Simulation results validate the efficacy of the proposed model.

Aspiring green agendas in conjunction with tremendous economic pressures are resulting in an increased attention to the environment and technological innovations for improving existing logistics systems. Last mile logistics, in particular, are becoming much more than a consumer convenience necessity and a transportation optimization exercise. Rather, this area presents a true opportunity to foster both financial and environmental sustainability. This paper investigates recent technological advancements and pending needs related to business and social innovations, emphasizing green logistics and city logistics concepts. We discuss various pertinent aspects, including drones, delivery robots, truck platooning, collection and pickup points, collaborative logistics, integrated transportation, decarbonization and advanced transport analytics. From a mathematical perspective, we focus on the basic features of the vehicle routing problem and some of its variants. We provide recommendations around strategies that may facilitate the adoption of new effective technologies and innovations.

Adopting unmanned aerial vehicles (UAV), also known as drones, into the last-mile-delivery sector and having them work alongside trucks with the aim of improving service quality and reducing the transportation cost gives rise to a new class of Vehicle Routing Problems (VRPs). In this paper, we introduce a new optimization problem called the min-cost Parallel Drone Scheduling Vehicle Routing Problem (PDSVRP). This problem is a variant of the well-known Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP) recently introduced in the literature in which we allow multiple trucks and consider the objective of minimizing the total transportation costs. We formulate the problem as a Mixed Integer Linear Program and then develop a Ruin and Recreate ( R & R ) algorithm. Exploiting PDSVRP solution characteristics in an effective manner, our heuristic manages to introduce “sufficient” rooms to a solution via new removal operators during the ruin phase. It is expected to enhance the possibilities for improving solutions later in the recreate phase. Multiple experiments on a new set of randomly generated instances confirm the performance of our approach. To explore the benefits of drone delivery as well as the insight into the impact of related factors on the contribution of drones’ use to operational cost, a sensitivity analysis is conducted. We also adapt the proposed algorithm to solve the PDSTSP and validate it via benchmarks available in the literature. It is shown that our algorithm outperforms state-of-the-art algorithms in terms of solution quality. Out of 90 considered instances, it finds 26 new best known solutions.

This paper introduces a complex real-world problem on a large scale that combines the split delivery heterogeneous vehicle routing problem with three-dimensional loading and considers new routing and loading constraints. The problem aims to find a set of routes with minimum transportation cost by satisfying the demand of all customers and loading constraints. We propose a column generation-based heuristic algorithm that employs three heuristic algorithms to solve the subproblem and a hybrid algorithm for loading. Computational experiments on the literature instances indicate that the proposed algorithm can produce very near solutions to the literature algorithm's solutions in significantly shorter running times. This paper introduces real-world instances with 230 to 850 customers, several times larger than the existing benchmarks. The results of the proposed algorithm for real-world instances are effective, and compared to the current situation, it leads to a reduction of 20% in the average total cost of transportation. Also, the average number of vehicles is reduced by 36%.

Today’s organizations have extreme pressure to continuously improve their performance. However, most of the improvements focus solely on the production side of the value chain, and great opportunities are missed because of this. Moreover, since the view is limited to production, important data to improve other areas of the value chain is left unused. This thesis focuses on overcoming this gap by proposing a case study in an automotive manufacturer, which intends to increase efficiency in both production and the factory’s Manufacturing Tool Repair support service. Due to this, the present work is divided into two workstreams: the production workstream and the support service workstream. For both workstreams the development of a decision support system is the proposed solution. In the production workstream this system is based on the e-Kanban methodology, which aims to inform the workers on what to produce, in which quantity and when. As part of this, a data collection system was created to gather real-time information from the production lines and strategically placed stock locations. The results for this workstream show the positive impact of the e-Kanban system in the reduction of stock levels and balanced distribution of components in these stocks. For the second workstream, the focus is to reduce the time workers of the Manufacturing Tool Repair support service spend picking and delivering manufacturing tools from and to the production lines, which is defined as a non-value adding activity. In this workstream the decision support system intends to inform the workers when to go on a pickup and delivery route, which route to follow and, which tools to pickup and deliver from each customer. All of this while minimizing the total traveling time. This problem is approached as a Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time windows, together with a Two-Dimensional Bin-Packing Problem both solved using two linear programming models. The data inputted into the models is obtained by the same data collection system developed for the e-Kanban. The tests show that by using this approach, the workers are able to reduce traveling times and obtain results within a low computational time, which makes it a suitable solution for daily operational use. As organizações atuais estão sujeitas a uma pressão extrema para melhorar continuamente a sua performance. No entanto, maior parte das melhorias realizadas focam-se apenas no lado produtivo da cadeia de valor, e por isso grandes oportunidades são perdidas. Além disso, como a visão se limita à produção, informação útil para melhorar outras áreas da cadeia de valor não é utilizada. Esta tese foca-se, precisamente, em colmatar esta lacuna, propondo um caso de estudo num fabricante da indústria automóvel, que pretende aumentar a sua eficiência tanto na produção como no serviço de apoio à Reparação de Ferramentas. Devido a isto, esta tese encontra-se divida em duas etapas: a etapa da produção e a etapa do serviço de apoio. Para ambas, a solução proposta foca-se no desenvolvimento de um sistema de apoio à decisão. Na etapa da produção, este sistema é baseado na metodologia do e-Kanban, e visa informar os trabalhadores sobre o que produzir, em que quantidade e quando. Para tal, foi criado um sistema de recolha de dados em tempo real nas linhas de produção e nos stocks estratégicos. Os resultados obtidos mostram uma redução dos níveis de stock e uma distribuição mais balanceada dos vários componentes nestes stocks. A segunda etapa foca-se em reduzir o tempo que os funcionários do serviço de Reparação de Ferramentas alocam à entrega e recolha de ferramentas nas linhas de produção, o que é considerado uma atividade de não valor acrescentado. Nesta etapa o sistema de apoio pretende informar os trabalhadores quando devem fazer uma rota de entrega e recolha, qual a rota a seguir e quais as ferramentas para entregar e recolher em cada cliente. Tudo isto, minimizando o tempo total de viagem. Este problema é abordado como um Problema de Rotas para Veículos com Entrega e Recolha Simultânea e Janelas Temporais e um Problema de Empacotamento bidimensional, ambos resolvidos recorrendo a modelos de programação linear. Os dados usados no modelo são recolhidos usando o mesmo sistema de recolha de dados desenvolvido para o e-Kanban. Os testes mostram que, usando esta abordagem, os trabalhadores são capazes de reduzir os tempos de viagem, sendo estes resultados obtidos num baixo tempo computacional, o que torna a solução adequada para o uso operacional diário. Programa Doutoral em Engenharia e Gestão Industrial

Funding Information: Inês A. Ferreira acknowledges the financial support from Fundação para a Ciência e Tecnologia (FCT) for funding PhD Grant-REF: SFRH/BD/145448/2019. Helena Carvalho acknowledges Fundação para a Ciência e Tecnologia (FCT) for its financial support through the project UIDB/00667/2020 (UNIDEMI). Carina Pimentel acknowledges Fundação para a Ciência e Tecnologia (FCT) within the R&D Units Project Scope UIDB/00319/2020. Publisher Copyright: © 2023 by the authors. The number of variants of the vehicle routing problem (VRP) has grown rapidly in the last decades. Among these, VRPs with time window constraints are among the most studied ones. However, the literature regarding VRPs that concerns the delivery and installation of products is scarce. The main aim of this study was to propose a heuristic approach for the route planning process of a company whose focus is on furniture delivery and assembly and, thus, contributing to the research around the Delivery and Installation Routing Problem. The case study method was used, and two scenarios were compared: the current scenario (showing the routes created by the company worker); and the future scenario (representing the routes created by the heuristic). Results show that the proposed heuristic approach provided a feasible solution to the problem, allowing it to affect customers and teams without compromising the teams’ competencies and respecting all constraints. publishersversion published

The state of Hawaii and island of Oahu are vulnerable to supply chain disruptions, such that any major disaster will require emergency food distribution to local populations. However, organizations across federal, state, and local government have proposed different distribution concepts that rely on different points of distribution (PODs), where no concept on their own may be sufficient to feed Oahu communities. In this work, we develop a data set and series of models to test these concepts for populations on Windward Oahu. We develop two models that select optimal POD locations for either a pickup concept, where populations drive to receive food, or a delivery concept, where food is brought to communities. We further study hybrid concepts that prefer either pickup or delivery. Our results show that ideal plans for Windward Oahu will prefer delivery PODs and utilize 17 hybrid PODs that serve both pickup and delivery purposes. Moreover, we identify four POD locations that would be used no matter which distribution concept is implemented. We recommend developing a hybrid distribution concept centered on delivery that can be tested and implemented at these four locations. Strategic Environmental Research and Development Program, 4800 Mark Center Drive, Suite 16F16, Alexandria, VA 22350-3605 Civilian, Department of the Navy Approved for public release. Distribution is unlimited.

This research discusses the goods distribution system in an urban area by considering an odd-even vehicle license plate rule. This rule enables the vehicles with the even-number plate to pass particular roads on even-number dates and vice versa during specific time intervals determined by the authority. This rule is potentially rising the company’s logistic cost up to 20%. Therefore, a Mixed-Integer Linear Programming model is developed to solve the problem. The performance of the model is tested on some numerical examples. Computational results show that the model generates optimal solutions with numerous computational times. The instances of customers located randomly and clustered manner (i.e., mix) are arduous to solve. The average computational time of these instances is 1 hour and 35 minutes.

With Mobility-as-a-Service platforms moving toward vertical service expansion, we propose a destination recommender system for Mobility-on-Demand (MOD) services that explicitly considers dynamic vehicle routing constraints as a form of a ``physical internet search engine''. It incorporates a routing algorithm to build vehicle routes and an upper confidence bound based algorithm for a generalized linear contextual bandit algorithm to identify alternatives which are acceptable to passengers. As a contextual bandit algorithm, the added context from the routing subproblem makes it unclear how effective learning is under such circumstances. We propose a new simulation experimental framework to evaluate the impact of adding the routing constraints to the destination recommender algorithm. The proposed algorithm is first tested on a 7 by 7 grid network and performs better than benchmarks that include random alternatives, selecting the highest rating, or selecting the destination with the smallest vehicle routing cost increase. The RecoMOD algorithm also reduces average increases in vehicle travel costs compared to using random or highest rating recommendation. Its application to Manhattan dataset with ratings for 1,012 destinations reveals that a higher customer arrival rate and faster vehicle speeds lead to better acceptance rates. While these two results sound contradictory, they provide important managerial insights for MOD operators.

We study tactical models for the design of same-day delivery (SDD) systems. Same-day fulfillment in e-commerce has seen substantial growth in recent years, and the underlying management of such services is complex. Although the literature includes operational models to study SDD, they tend to be detailed, complex, and computationally difficult to solve, and thus may not provide any insight into tactical SDD design variables and their impact on the average performance of the system. We propose a simplified vehicle-dispatching model that captures the “average” behavior of an SDD system from a single stocking location by utilizing continuous approximation techniques. We analyze the structure of optimal vehicle-dispatching policies given our model for two important instance families—the single-vehicle case and the case in which the delivery fleet is large—and develop techniques to find these policies that require only simple computations. We also leverage these results to analyze the case of a finite fleet, proposing a heuristic policy with a worst-case approximation guarantee. We then demonstrate with several example problem settings how this model and these policies can help answer various tactical design questions, including how to select a fleet size, determine an order cutoff time, and combine SDD and overnight order delivery operations. We validate model predictions empirically against a detailed operational model in a computational case study using geographic and Census data for the northeastern metro Atlanta region, and we demonstrate that our model predicts the average number of orders served and dispatch time to within 1%. This paper was accepted by Jay Swaminathan, operations management.

Stochastic dynamic vehicle routing problems have become an essential part of logistics and mobility services. In such problems, a sequence of vehicle routing decisions has to be made in reaction and anticipation of newly revealed stochastic information. To this end, a variety of computational operations research methods has emerged in the literature, increasingly integrating potential future information in their decision making. The integration of information models into decision models via computational methods is known as prescriptive analytics, the most recent advance of business analytics. In this paper, we explore the existing work and future potential of prescriptive analytics for stochastic dynamic vehicle routing. We identify the characteristics of decision models and information models unique in stochastic dynamic vehicle routing and analyze how different methodology meets the characteristics' requirements. We use the insights to derive recommendations about promising methodology when approaching specific stochastic dynamic vehicle routing problems.

Automated driving technology is one of the emerging technologies which will change the transportation mode in the future. Distributing the automated driving vehicles from the automobile factory to dealers has a huge difference compared with traditional vehicles. This paper considers the variety of cases where the automated driving vehicles can be both distribution tools and distribution goods. Then establishes a new distribution model that integrates self-distribution of autonomous vehicles into the existing distribution rings form a complex network composed of ring-branches. This cooperative distribution model of automated driving and traditional vehicle transport to minimize transportation cost and maximize the overall efficiency. Furthermore, we design an improved adaptive large neighborhood algorithm (ALNS) to solve the model which combines the merger heuristics and splitter heuristics to promote generate the optimal solutions. The efficiency of our proposed method is proved by real-world data from an automobile enterprise. Additionally, the sensitivity analysis of the maximum distance for automated driving vehicles to be delivered by themselves suggests that the larger distance, the more outstanding of cost reduction and efficiency increase for our proposed model.

One problem in collaborative pickup delivery problem (PDP) was excessive outsourced jobs. It happened in many studies on the collaborative PDP. Besides, the revenue sharing in it was unclear although important. This work aimed to propose a novel collaborative PDP model which minimizes total travel distance while maintains low outsourced jobs. It proposed several contributions. First, it prioritized internal jobs first rather than full collaborative model. Second, it proposed new revenue sharing model. It adopted cluster-first route-second and mixed pickup and delivery. It was developed by combining the genetic algorithm and nearest distance algorithm where the genetic algorithm was used in the clustering process and the nearest distance was used in the routing process. The simulation result shows that the proposed model was better than the comparing models: (1) combined K-means and genetic algorithm model (KMGA) and (2) combined simulated annealing and last-in first-out (SNLIFO) model. When the number of orders was high (300 units), the total travel distance of the proposed model was 37 percent lower than the KMGA model and 30 percent lower than the SNLIFO model. In average, the outsourcing rate of the proposed model was 70 percent lower than the previous models.

When transporting goods, truck drivers may have to perform load transfers between two vehicles at cross-dock or transfer locations. These transfers create interdependencies between the routes of different truck drivers and require careful temporal synchronization. The situation becomes even more complicated when driver schedules must comply with customer time windows, working periods and regulatory resting requirements. Although the scheduling of hours of service for truck drivers is a well-known problem, existing algorithms cannot cope with interdependent routes. We introduce the Truck Driver Scheduling Problem with Interdependent Routes to successfully accommodate this real-world characteristic. This paper proposes a mathematical model and a label propagation algorithm to solve this new problem under the regulations of the European Union. Experiments indicate that the algorithm can quickly schedule a large number of interdependent routes and outperforms a mathematical programming approach. The algorithm produces valid schedules for multiple drivers and thus becomes a foundation for future vehicle routing algorithms that address interdependent routes and hours of service regulations. ispartof: European Journal Of Operational Research vol:298 issue:1 pages:76-88 status: published

Hours of service (HOS) regulations are among the conventional safety constraints that are compiled by long-haul truck drivers. These regulations have been considered in models and algorithms of vehicle routing problems to assign safe schedules to drivers. However, the HOS regulations neglect a few crucial fatigue risk factors and, at times, fail to generate fatigue-reducing schedules. In this study, a set of biomathematical fatigue constraints (BFCs) derived from biomathematical models are considered for a long-haul vehicle routing and scheduling problem. A BFC scheduling algorithm and a BFC-HOS scheduling algorithm have been developed and then embedded within a tabu search heuristic to solve the combined vehicle routing and scheduling problem. All the solution methods have been tested on modified Solomon instances and a real-life instance, and the computational results confirm the advantages of employing a sophisticated and fatigue-reducing scheduling procedure when planning long-haul transportation.

In this work, we study, model, and propose two approaches to solve a raw milk transportation problem inspired by a real case of a milk company in Chile. The milk is produced by a set of farms scattered in a large rural area. The company must collect all the production daily using a truck fleet. We address the location of milk collection centers to reduce transportation costs. Each center has a limited capacity and a reduced truck fleet, composed of small trucks, to collect a substantial proportion of the produced milk. Once the milk is accumulated in the collection centers, a fleet of big trucks, traveling from a processing plant, collects the milk of each collection center and some large farms. We propose a mixed-integer linear programming model, a three-stage approach based on mathematical models, and an iterated local search approach to face this problem. We evaluate these approaches’ performance using a small case and several real-world examples, including a clustering approach to divide the instance into small sub-instances. The results obtained for the real-world instance show improvements of up to 10% percent when milk collection centers are allowed.

We study a new variant of the vehicle routing problem, which arises in hospital-wide scheduling of physical therapists. Multiple service locations exist for patients, and resource synchronization for the location capacities is required as only a limited number of patients can be treated at one location at a time. Additionally, operations synchronization between treatments is required as precedence relations exist. We develop an innovative exact branch-price-and-cut algorithm including two approaches targeting the synchronization constraints (1) based on branching on time windows and (2) based on adding combinatorial Benders cuts. We optimally solve realistic hospital instances with up to 120 treatments and find that branching on time windows performs better than adding cutting planes. Summary of Contribution: We present an exact branch-price-and-cut (BPC) algorithm for the therapist scheduling and routing problem (ThSRP), a daily planning problem arising at almost every hospital. The difficulty of this problem stems from its inherent structure that features routing and scheduling while considering multiple possible service locations with time-dependent location capacities. We model the ThSRP as a vehicle routing problem with time windows and flexible delivery locations and synchronization constraints, which are properties relevant to other vehicle routing problem variants as well. In our computational study, we show that the proposed exact BPC algorithm is capable of solving realistic hospital instances and can, thus, be used by hospital planners to derive better schedules with less manual work. Moreover, we show that time window branching can be a valid alternative to cutting planes when addressing synchronization constraints in a BPC algorithm.

Emerging hydrogen energy storage technologies present a potential opportunity to increase the flexibility and resiliency of the integrated power and transportation system with ultra-high penetration of renewable energy. This paper studies a conceptual integrated energy-mobility system (IEMS) based on renewable-to-hydrogen stations (RHSs) and tank truck fleets. In an RHS, the renewables power the grid while also charge a hydrogen energy storage unit that can perform power-to-hydrogen (P2H) and hydrogen-to-power (H2P) operations. Besides, using tank truck fleets, the RHS will distribute its surplus hydrogen products to local consumers, e.g., refueling stations serving hydrogen fuel cell vehicles. The operation framework of the IEMS is analyzed, and some preprocessing technologies are developed to reduce modeling complexity, then, a joint optimal scheduling model, involving renewable generation contract, P2H, and H2P of the station, hydrogen product demands of the local consumers, vehicle routing problem of the truck fleets, is established. Afterward, the formulated problem is solved by a heuristic method based on the Exhaustive Search and Genetic Algorithm. Numerical results verify the effectiveness of the joint optimal scheduling model and illustrate that the IEMS has the potentials to promote hydrogen-integrated transportation and power systems.

We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.

The time-dependent shortest path and vehicle routing literature depends on realistic and reasonable test data for demonstration and performance evaluation. Despite the advancements in GPS and tracking technologies there is still lack and inaccessibility of publicly available real-world road networks with time-dependent arc costs and speeds. Since most of the time-dependent travel time layer generation models proposed for vehicle routing problems (VRPs) are mainly developed for synthetic networks, they cannot capture some realistic features of the real road networks and cannot be used in time-dependent shortest path problems (TDSPPs). In this paper, we first exploit spatial and temporal behavior of travel times using real life road network and speed data, and discuss the cases where the existing methods in the literature are not applicable. Then, we propose an enhanced method that is best fitted for TDSPP and time-dependent VRP (TDVRP). The proposed method can be implemented on both synthetic and real road networks. Finally, we apply our method to generate realistic speed data on Istanbul road network and demonstrate the applicability in TDSPP and TDVRP.

The option of decarbonizing urban freight transport using Battery Electric Vehicle (BEV) seems promising.However, there is currently a strong debate whether Fuel Cell Electric Vehicle (FCEV) might be the bettersolution. The question arises as to how a fleet of FCEV influences the operating cost, the Greenhouse Gas(GHG) emissions and primary energy demand in comparison to BEVs and to Internal Combustion EngineVehicle (ICEV). To investigate this, we simulate the urban food retailing as a representative share of urbanfreight transport using a multi-agent transport simulation software. Synthetic routes as well as fleet size andcomposition are determined by solving a Vehicle Routing Problem (VRP). We compute the operating costsusing a total cost of ownership (Total Cost of Ownership (TCO)) analysis and the use phase emissions as wellas primary energy demand using the Well To Wheel (WTW) approach. While a change to BEV results in 17 -23% higher costs compared to ICEV, using FCEVs leads to 22 - 57% higher costs. Assuming today’s electricitymix, we show a GHG emission reduction of 25% compared to the ICEV base case when using BEV. Currenthydrogen production leads to a GHG reduction of 33% when using FCEV which however cannot be scaled tolarger fleets. Using current electricity in electrolysis will increase GHG emission by 60% compared to the basecase. Assuming 100% renewable electricity for charging and hydrogen production, the reduction from FCEVsrises to 73% and from BEV to 92%. The primary energy requirement for BEV is in all cases lower and forhigher compared to the base case. We conclude that while FCEV have a slightly higher GHG savings potentialwith current hydrogen, BEV are the favored technology for urban freight transport from an economic andecological point of view, considering the increasing shares of renewable energies in the grid mix.

The Vehicle Routing Problem (VRP) is a well-known NP-hard combinatorial optimization problem, which has wide spread applications in real world, such as logistics, bus route planning, and urban path planning. To solve VRP, traditional optimization methods usually start the search from scratch and ignore the VRPs solved in the past, which could lead to repeated explorations of the search space of related problems, and thus results in slow optimization process involving unnecessary computational cost. Keeping this in mind, to speed up the optimization for vehicle routing, this article presents a new study towards faster vehicle routing by transferring knowledge from customer representations which are learned from past solved VRPs. In particular, we propose to capture the useful traits buried in previous optimized routing solutions by learning a new customer representation, which can be transferred across VRPs, serving as the prior knowledge, to bias the optimization in the target VRP. In contrast to existing approaches, the proposed knowledge transfer is consist of a learning of new customer representation based on the optimized routing solution, which is general to VRPs possessing different structural properties, and a weighted l₁ norm-regularized formulation for building sparse mapping across VRPs, that is easy to solve. Further, the proposed knowledge transfer across VRPs occurs along the whole optimization search process, and is thus able to guide the routing optimization process consistently. To verify the efficacy of the proposed method, by using population-based optimization method as the VRP solver, comprehensive empirical studies on both commonly used VRP benchmarks and real world vehicle routing application are presented.

This letter proposes a fast Unmanned Aerial Vehicle (UAV) trajectory planning algorithm based on the Fermat-point theory in maritime Internet of Things systems. Specifically, we first construct Delaunay triangles based on the deployment of unmanned surface vehicles. Then, the Fermat point of each Delaunay triangle is calculated and as a hovering point of UAVs to improve the channel condition. Finally, the trajectory planning problem can be transformed into a vehicle routing problem with pickup, which is solved by the proposed algorithm based on C-W saving method. Simulation results show the proposed algorithm can efficiently increase collected data volume of UAVs.

In traditional parcel delivery operations, customers determine delivery locations and, hence, the performance of a transporter. We exploit this idea and show that customers can improve the efficiency of a transporter by giving the latter flexibility in choosing the delivery locations. Two possible policies to enable this flexibility are presented and evaluated. The first policy, conceptually similar to roaming vehicle routing, is related to the presence of alternative locations. The second policy is related to the possibility of aggregating/skipping some locations. We show that route optimization behind both policies can be modelled via the well-known generalized travelling salesman problem. Extensive computational experiments with real parcel delivery data are performed to evaluate the potential of the presented policies and to obtain insights for possible implementation in daily practice. The experiments show that under certain conditions, the two proposed policies can lead to 15 to 20% improvement in the route length and in extreme yet realistic cases up to 40 to 50%. Consequently, the concept of flexible delivery locations has potential for practice, especially in densely populated areas.