Approaching the Traveling Tournament Problem with Randomized Beam Search.

The traveling tournament problem is a well-known sports league scheduling problem famous for its practical hardness. Given an even number of teams with symmetric distances between their venues, a double round-robin tournament has to be scheduled minimizing the total travel distances over all teams. We consider the most common constrained variant without repeaters and a streak limit of three, for which we study a beam search approach based on a state-space formulation guided by heuristics derived from different lower bound variants. We solve the arising capacitated vehicle routing subproblems either exactly for small- to medium-sized instances up to 18 teams or heuristically also for larger instances up to 24 teams. In a randomized variant of the search, we employ random team ordering and add small amounts of Gaussian noise to the nodes' guidance for diversification when multiple runs are performed. This allows for a simple yet effective parallelization of the beam search. A final comparison is done on the NL, CIRC, NFL, and GALAXY benchmark instances with 12 to 24 teams, for which we report a mean gap difference to the best known feasible solutions of 1.2% and five new best feasible solutions.

An Entropy-Balanced Orthogonal Learning Bamboo Forest Growth Optimization Algorithm with Quasi-Affine Transformation Evolutionary and Its Application in Capacitated Vehicle Routing Problem.

The bamboo forest growth optimization (BFGO) algorithm combines the characteristics of the bamboo forest growth process with the optimization course of the algorithm. The algorithm performs well in dealing with optimization problems, but its exploitation ability is not outstanding. Therefore, a new heuristic algorithm named orthogonal learning quasi-affine transformation evolutionary bamboo forest growth optimization (OQBFGO) algorithm is proposed in this work. This algorithm combines the quasi-affine transformation evolution algorithm to expand the particle distribution range, a process of entropy increase that can significantly improve particle searchability. The algorithm also uses an orthogonal learning strategy to accurately aggregate particles from a chaotic state, which can be an entropy reduction process that can more accurately perform global development. OQBFGO algorithm, BFGO algorithm, quasi-affine transformation evolutionary bamboo growth optimization (QBFGO) algorithm, orthogonal learning bamboo growth optimization (OBFGO) algorithm, and three other mature algorithms are tested on the CEC2017 benchmark function. The experimental results show that the OQBFGO algorithm is superior to the above algorithms. Then, OQBFGO is used to solve the capacitated vehicle routing problem. The results show that OQBFGO can obtain better results than other algorithms.

Emergency logistics network optimization with time window assignment.

During natural disasters or accidents, an emergency logistics network aims to ensure the distribution of relief supplies to victims in time and efficiently. When the coronavirus disease 2019 (COVID-19) emerged, the government closed the outbreak areas to control the risk of transmission. The closed areas were divided into high-risk and middle-/low-risk areas, and travel restrictions were enforced in the different risk areas. The distribution of daily essential supplies to residents in the closed areas became a major challenge for the government. This study introduces a new variant of the vehicle routing problem with travel restrictions in closed areas called the two-echelon emergency vehicle routing problem with time window assignment (2E-EVRPTWA). 2E-EVRPTWA involves transporting goods from distribution centers (DCs) to satellites in high-risk areas in the first echelon and delivering goods from DCs or satellites to customers in the second echelon. Vehicle sharing and time window assignment (TWA) strategies are applied to optimize the transportation resource configuration and improve the operational efficiency of the emergency logistics network. A tri-objective mathematical model for 2E-EVRPTWA is also constructed to minimize the total operating cost, total delivery time, and number of vehicles. A multi-objective adaptive large neighborhood search with split algorithm (MOALNS-SA) is proposed to obtain the Pareto optimal solution for 2E-EVRPTWA. The split algorithm (SA) calculates the objective values associated with each solution and assigns multiple trips to shared vehicles. A non-dominated sorting strategy is used to retain the optimal labels obtained with the SA algorithm and evaluate the quality of the multi-objective solution. The TWA strategy embedded in MOALNS-SA assigns appropriate candidate time windows to customers. The proposed MOALNS-SA produces results that are comparable with the CPLEX solver and those of the self-learning non-dominated sorting genetic algorithm-II, multi-objective ant colony algorithm, and multi-objective particle swarm optimization algorithm for 2E-EVRPTWA. A real-world COVID-19 case study from Chongqing City, China, is performed to test the performance of the proposed model and algorithm. This study helps the government and logistics enterprises design an efficient, collaborative, emergency logistics network, and promote the healthy and sustainable development of cities.

How to achieve sustainable distribution in the fast fashion industry? An electric vehicle solution under the "vehicle-battery separation" mode.

Exploring sustainable urban distribution based on electric vehicles is crucial given the rise in global greenhouse gas emissions, especially for fast fashion industries with extremely high distribution frequencies. However, most studies have overlooked the impact of deep discharge on the distribution route scheme, and few studies fit the characteristics of the fast fashion industry. As a result, this study presents a novel electric vehicle routing problem considering deep discharge model (EVRP-DD) for distribution route optimization, which fully considers deep discharge under the emerging mode of vehicle-battery separation. The characteristics of fashion consumers and products were also integrated into the model, such as consumer satisfaction and 3D loading constraints. To solve this complex programming problem, a sophisticated hybrid ant colony optimization (HACO) algorithm was designed by combining the advantages of ACO and A-star algorithms. Using real-life data, the experimental results verify the effectiveness and superiority of the proposed solution. EVRP-DD achieved reduced driving distance, total distribution cost, and deep discharge distance. HACO can enhance the computation speed and reduce the total distribution cost compared with the two conventional algorithms. The proposed solution showed excellent flexibility and could effectively adjust the optimal route scheme according to the ever-changing external environment. Thus, it can be concluded that this solution is a powerful tool for enterprises to achieve sustainable distribution. This study has realized theoretical innovation in sustainable distribution under the new mode of vehicle-battery separation, and its successful application in the fast fashion industry reflects its valuable application value.

Algorithm for DNA sequence assembly by quantum annealing.

BACKGROUND: The assembly task is an indispensable step in sequencing genomes of new organisms and studying structural genomic changes. In recent years, the dynamic development of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool used, for example, in medical diagnostics. However, this is hampered by the slowness and computational requirements of the current processing algorithms, which raises the need to develop more efficient algorithms. One possible approach, still little explored, is the use of quantum computing. RESULTS: We present a proof of concept of de novo assembly algorithm, using the Genomic Signal Processing approach, detecting overlaps between DNA reads by calculating the Pearson correlation coefficient and formulating the assembly problem as an optimization task (Traveling Salesman Problem). Computations performed on a classic computer were compared with the results achieved by a hybrid method combining CPU and QPU calculations. For this purpose quantum annealer by D-Wave was used. The experiments were performed with artificially generated data and DNA reads coming from a simulator, with actual organism genomes used as input sequences. To our knowledge, this work is one of the few where actual sequences of organisms were used to study the de novo assembly task on quantum annealer. CONCLUSIONS: Proof of concept carried out by us showed that the use of quantum annealer (QA) for the de novo assembly task might be a promising alternative to the computations performed in the classical model. The current computing power of the available devices requires a hybrid approach (combining CPU and QPU computations). The next step may be developing a hybrid algorithm strictly dedicated to the de novo assembly task, using its specificity (e.g. the sparsity and bounded degree of the overlap-layout-consensus graph).

Vehicle-Assisted UAV Delivery Scheme Considering Energy Consumption for Instant Delivery.

Unmanned aerial vehicles (UAVs) are increasingly used in instant delivery scenarios. The combined delivery of vehicles and UAVs has many advantages compared to their respective separate delivery, which can greatly improve delivery efficiency. Although a few studies in the literature have explored the issue of vehicle-assisted UAV delivery, we did not find any studies on the scenario of an UAV serving several customers. This study aims to design a new vehicle-assisted UAV delivery solution that allows UAVs to serve multiple customers in a single take-off and takes energy consumption into account. A multi-UAV task allocation model and a vehicle path planning model were established to determine the task allocation of the UAVs as well as the path of UAVs and the vehicle, respectively. The model also considered the impact of changing the payload of the UAV on energy consumption, bringing the results closer to reality. Finally, a hybrid heuristic algorithm based on an improved K-means algorithm and ant colony optimization (ACO) was proposed to solve the problem, and the effectiveness of the scheme was proven by multi-scale experimental instances and comparative experiments.

Waste collection routing problem: A mini-review of recent heuristic approaches and applications.

The waste collection routing problem (WCRP) can be defined as a problem of designing a route to serve all of the customers (represented as nodes) with the least total traveling time or distance, served by the least number of vehicles under specific constraints, such as vehicle capacity. The relevance of WCRP is rising due to its increased waste generation and all the challenges involved in its efficient disposal. This research provides a mini-review of the latest approaches and its application in the collection and routing of waste. Several metaheuristic algorithms are reviewed, such as ant colony optimization, simulated annealing, genetic algorithm, large neighborhood search, greedy randomized adaptive search procedures, and others. Some other approaches to solve WCRP like GIS is also introduced. Finally, a performance comparison of a real-world benchmark is presented as well as future research opportunities in WCRP field.

An empirical evaluation of a novel domain-specific language - modelling vehicle routing problems with Athos.

Domain-specific languages (DSLs) are a popular approach among software engineers who demand for a tailored development interface. A DSL-based approach allows to encapsulate the intricacies of the target platform in transformations that turn DSL models into executable software code. Often, DSLs are even claimed to reduce development complexity to a level that allows them to be successfully applied by domain-experts with limited programming knowledge. Recent research has produced some scientifically backed insights on the benefits and limitations of DSLs. Further empirical studies are required to build a sufficient body of knowledge from which support for different claims related to DSLs can be derived. In this research study, we adopt current DSL evaluation approaches to investigate potential gains in terms of effectiveness and efficiency, through the application of our DSL Athos, a language developed for the domain of traffic and transportation simulation and optimisation. We compare Athos to the alternative of using an application library defined within a general-purpose language (GPL). We specified two sets of structurally identical tasks from the domain of vehicle routing problems and asked study groups with differing levels of programming knowledge to solve the tasks with the two approaches. The results show that inexperienced participants achieved considerable gains in effectiveness and efficiency with the usage of Athos DSL. Though hinting at Athos being the more efficient approach, the results were less distinct for more experienced programmers. The vast majority of participants stated to prefer working with Athos over the usage of the presented GPL's API. Supplementary Information: The online version contains supplementary material available at 10.1007/s10664-022-10210-whttps://doi.org/10.1007/s10664-022-10210-w.

Home care vehicle routing problem with chargeable overtime and strict and soft preference matching.

A new scheduling problem arising in the home care context is addressed, whose novelty with respect to the literature lies in the way overtime is paid. In this problem, some clients are willing to pay a higher fee to cover the additional overtime cost, if such overtime is incurred because a caregiver works extra time with the client to preserve continuity of care. These overtime hours charged to clients unburden the company, which no longer has to balance between cost and continuity of care in a traditional way. The problem is also studied in a context that includes preferences expressed by both clients and caregivers. Strict preferences must be respected with a high priority, while soft preferences increase the satisfaction and should be preferably respected. We formalize the problem as a Mixed Integer Linear Problem and also propose a cluster-based decomposition to solve real-life instances. The problem is inspired by the real case study of a provider operating in the USA. Numerical results validate the model and confirm the capability of the decomposition approach to deal with real-life instances.

An Optimal Routing Algorithm for Unmanned Aerial Vehicles.

A delivery service using unmanned aerial vehicles (UAVs) has potential as a future business opportunity, due to its speed, safety and low-environmental impact. To operate a UAV delivery network, a management system is required to optimize UAV delivery routes. Therefore, we create a routing algorithm to find optimal round-trip routes for UAVs, which deliver goods from depots to customers. Optimal routes per UAV are determined by minimizing delivery distances considering the maximum range and loading capacity of the UAV. In order to accomplish this, we propose an algorithm with four steps. First, we build a virtual network to describe the realistic environment that UAVs would encounter during operation. Second, we determine the optimal number of in-service UAVs per depot. Third, we eliminate subtours, which are infeasible routes, using flow variables part of the constraints. Fourth, we allocate UAVs to customers minimizing delivery distances from depots to customers. In this process, we allow multiple UAVs to deliver goods to one customer at the same time. Finally, we verify that our algorithm can determine the number of UAVs in service per depot, round-trip routes for UAVs, and allocate UAVs to customers to deliver at the minimum cost.

Constrained Fitness Landscape Analysis of Capacitated Vehicle Routing Problems.

Vehicle Routing Problems (VRP) comprise many variants obtained by adding to the original problem constraints representing diverse system characteristics. Different variants are widely studied in the literature; however, the impact that these constraints have on the structure of the search space associated with the problem is unknown, and so is their influence on the performance of search algorithms used to solve it. This article explores how assignation constraints (such as a limited vehicle capacity) impact VRP by disturbing the network structure defined by the solution space and the local operators in use. This research focuses on Fitness Landscape Analysis for the multiple Traveling Salesman Problem (m-TSP) and Capacitated VRP (CVRP). We propose a new Fitness Landscape Analysis measure that provides valuable information to characterize the fitness landscape's structure under specific scenarios and obtain several relationships between the fitness landscape's structure and the algorithmic performance.

A sustainable medical waste collection and transportation model for pandemics.

We are currently experiencing a critical period for the prevention and control of the COVID-19 pandemic. COVID-19 related waste is a threat to global public environmental health. Medical waste management during this pandemic is one of the major issues facing public service organizations such as municipalities, which is of great importance in terms of logistics, environment and social aspects. The discussion of logistics operations is related to the collection, transportation and disposal of waste, which imposes high expenses. Many methods have been applied to develop and improve waste management policies in the literature. Apart from these studies, very few researchers have improved vehicle operations in waste management considering environmental aspects and the possibility of outsourcing. In this paper, by examining the gaps in the field, we try to explain and formulate the sustainable medical waste management problem for pandemics. Finally, by designing several practical examples with different scales, we solve the problem using CPLEX solver, compare different conditions and discuss the practical implications using the sensitivity analysis of demand parameter.

Municipal solid waste transfer station planning through vehicle routing problem-based scenario analysis.

Collection, transfer and transport of municipal solid waste (MSW) is one of the most challenging tasks of local municipalities and occupies a significant portion of the municipal expenses. Appropriately planned transfer stations (TSs) can increase system performance and reduce costs. Therefore, this study aims to develop a spatial modelling approach for investigating the optimum siting and economic impacts of MSW TSs. A geographic information system-based land suitability analysis was conducted to identify potential TS sites followed by a scenario analysis to determine optimum TS sites and waste collection routes for various collection vehicle capacities through vehicle routing problem modelling. The approach was implemented in the southeastern region of Izmir where a new landfill is to be built to serve three district municipalities. The addition of a TS in the study area reduced the collection time and number of shifts by 9%. Similarly, collection with large vehicles decreased the collection time and number of shifts by 25% and 17%, respectively. However, the unit cost of the system increased from 17.52 to 18.60 US$ metric tonnes-1 waste with the TS addition because of the additional costs of the TS. The results indicated that TS addition is not economically feasible in the study area because of the small collection vehicle fleet (eight collection vehicles), proximity of landfill to areas with high waste density and district level collection. On the other hand, TS addition resulted in lower fuel consumption which may help reduce fuel-induced air pollution.

A Review of Data Analytic Applications in Road Traffic Safety. Part 2: Prescriptive Modeling.

In the first part of the review, we observed that there exists a significant gap between the predictive and prescriptive models pertaining to crash risk prediction and minimization, respectively. In this part, we review and categorize the optimization/ prescriptive analytic models that focus on minimizing crash risk. Although the majority of works in this segment of the literature are related to the hazardous materials (hazmat) trucking problems, we show that (with some exceptions) many can also be utilized in non-hazmat scenarios. In an effort to highlight the effect of crash risk prediction model on the accumulated risk obtained from the prescriptive model, we present a simulated example where we utilize four risk indicators (obtained from logistic regression, Poisson regression, XGBoost, and neural network) in the k-shortest path algorithm. From our example, we demonstrate two major designed takeaways: (a) the shortest path may not always result in the lowest crash risk, and (b) a similarity in overall predictive performance may not always translate to similar outcomes from the prescriptive models. Based on the review and example, we highlight several avenues for future research.

A trilevel r-interdiction selective multi-depot vehicle routing problem with depot protection.

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

Sustainable location and route planning with GIS for waste sorting centers, case study: Kerman, Iran.

One of the important issues in the world is the significant growth of waste production, including waste that is not biodegradable in nature. According to the Kerman Municipality, 440 tonnes of municipal waste is collected daily in Kerman consisting of five major parts of paper, plastic, metal, glass, and wet waste. The major problems of municipal solid waste disposal are soil erosion, air pollution, and greenhouse gas emissions. The most important factors related to recycling are waste sorting and the relevant environmental conditions. This study aims to create a sustainable approach by locating the optimal sites to reduce environmental pollution, decrease costs, and improve the service system to the society. Optimal locations for establishing the collecting and sorting centers in the city are specified by the use of geographic information system software, based on criteria consisting of population density, road network, distance to health centers, distance to disposal center, waste sorting culture, land space, and land cost, which were weighted by an analytical hierarchy process. It was noteworthy that the criterion "waste sorting culture", which has a foundation in human sciences and sociology, has been considered by experts in this study to be of the highest importance among other criteria at locating sorting centers. Subsequently, using a symmetric capacitated vehicle routing problem, the number and capacity of each vehicle are determined to serve the specified locations according to the economic, social, and environmental constraints.

Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study.

This paper studies a multi-trip vehicle routing problem with time windows specifically related to urban waste collection. Urban waste collection is one of the municipal activities with large costs and has many practical difficulties. In other words, waste collection and disposal is a costly task due to high operating expenses (fuel, maintenance, recycling, manpower, etc.) and small improvements in this field can result in tremendous savings on municipal expenditure. In the raised problem, the goal is to minimize total cost including traversing cost, vehicle employment cost, and exit penalty from permissible time windows. In this problem, the waste is deposited at the points indicating the demand nodes, in which each demand shows the volume of generated waste. Considering multiple trips for vehicles and time windows are the most critical features of the problem, so that the priorities of serving some specific places such as hospitals can be observed. Since vehicle routing problems (VRP) belongs to NP-hard problems, an efficient simulated annealing (SA) is proposed to solve the problem. The computational results show that our proposed algorithm has a great performance in a short computational time in comparison with the CPLEX solver. Finally, in order to demonstrate the applicability of the model, a case study is analyzed in Iran, and the optimal policies are presented.

Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem.

In this paper, we compare different formulations of the multi-depot fleet size and mix vehicle routing problem (MDFSMVRP). This problem extends the multi-depot vehicle routing problem and the fleet size and mix vehicle routing problem, two logistics problems that have been extensively studied for many decades. This difficult vehicle routing problem combines complex assignment and routing decisions under the objective of minimizing fixed vehicle costs and variable routing costs. We first propose five distinct formulations to model the MDFSMVRP. We introduce a three-index formulation with an explicit vehicle index and a two-index formulation in which only vehicle types are identified. Other formulations are obtained by defining aggregated and disaggregated loading variables. The last formulation makes use of capacity-indexed variables. For each formulation, we summarize known and propose new valid inequalities, including symmetry breaking, lexicographic ordering, routing, and rounded capacity cuts. We then implement branch-and-cut and branch-and-bound algorithms for these formulations, and we fed them into a general purpose solver. We compare the bounds provided by the formulations on a commonly used set of instances in the MDFSMVRP literature, containing up to nine depots and 360 customers, and on newly generated instances. Our in-depth analysis of the five formulations shows which formulations tend to perform better on each type of instance. Moreover, our results have considerably improved available lower bounds on all instances and significantly improved quality of upper bounds that can be obtained by means of currently available methods.

Dynamic vehicle routing with time windows in theory and practice.

The vehicle routing problem is a classical combinatorial optimization problem. This work is about a variant of the vehicle routing problem with dynamically changing orders and time windows. In real-world applications often the demands change during operation time. New orders occur and others are canceled. In this case new schedules need to be generated on-the-fly. Online optimization algorithms for dynamical vehicle routing address this problem but so far they do not consider time windows. Moreover, to match the scenarios found in real-world problems adaptations of benchmarks are required. In this paper, a practical problem is modeled based on the procedure of daily routing of a delivery company. New orders by customers are introduced dynamically during the working day and need to be integrated into the schedule. A multiple ant colony algorithm combined with powerful local search procedures is proposed to solve the dynamic vehicle routing problem with time windows. The performance is tested on a new benchmark based on simulations of a working day. The problems are taken from Solomon's benchmarks but a certain percentage of the orders are only revealed to the algorithm during operation time. Different versions of the MACS algorithm are tested and a high performing variant is identified. Finally, the algorithm is tested in situ: In a field study, the algorithm schedules a fleet of cars for a surveillance company. We compare the performance of the algorithm to that of the procedure used by the company and we summarize insights gained from the implementation of the real-world study. The results show that the multiple ant colony algorithm can get a much better solution on the academic benchmark problem and also can be integrated in a real-world environment.

A novel approach to find and optimize bin locations and collection routes using a geographic information system.

One of the major challenges in big cities is planning and implementation of an optimized, integrated solid waste management system. This optimization is crucial if environmental problems are to be prevented and the expenses to be reduced. A solid waste management system consists of many stages including collection, transfer and disposal. In this research, an integrated model was proposed and used to optimize two functional elements of municipal solid waste management (storage and collection systems) in the Ahmadabad neighbourhood located in the City of Mashhad - Iran. The integrated model was performed by modelling and solving the location allocation problem and capacitated vehicle routing problem (CVRP) through Geographic Information Systems (GIS). The results showed that the current collection system is not efficient owing to its incompatibility with the existing urban structure and population distribution. Application of the proposed model could significantly improve the storage and collection system. Based on the results of minimizing facilities analyses, scenarios with 100, 150 and 180 m walking distance were considered to find optimal bin locations for Alamdasht, C-metri and Koohsangi. The total number of daily collection tours was reduced to seven as compared to the eight tours carried out in the current system (12.50% reduction). In addition, the total number of required crews was minimized and reduced by 41.70% (24 crews in the current collection system vs 14 in the system provided by the model). The total collection vehicle routing was also optimized such that the total travelled distances during night and day working shifts was cut back by 53%.