Ride-hailing companies will face the emergence and gradual expansion of AVs-only zones in urban areas where only automated vehicles (AVs) are allowed to circulate. When owning a mixed fleet (automated and conventional taxis), a ride-hailing company has to determine the optimal fleet size as a function of the gradually expanding coverage of AVs-only zones while taking into account interactions with privately-owned human-driven vehicles. To model this problem, we propose a bi-level framework in which the lower level captures the mixed routing behaviour of the vehicles and the endogenous traffic congestion, and the upper level determines fleet sizes to maximise profit. A parallel genetic algorithm is introduced to solve this bi-level framework, which is embedded with a tailored algorithm for solving the lower-level model. Numerical experiments are conducted on instances based on a small network and the network of the city of Delft, The Netherlands, to demonstrate the performance of the proposed solution method and investigate the impacts of AVs-only zones on traffic and ride-hailing operations. Results indicate that the fleet size of automated taxis increases nonlinearly with the expansion of the AVs-only zone while that of conventional taxis decreases as demand shifts from human-driven vehicles to automated taxis. The fleet size decision depends heavily on the fleet's cost structure, the location and the distribution of parking depots. Furthermore, the existence of an AVs-only zone leads to detours for human-driven vehicles in the early stages, but it will bring major benefits by reducing congestion as its size increases.

@en

The Resource Constrained Project Scheduling Problem with a flexible Project Structure (RCPSP-PS) is a generalization of the Resource Constrained Project Scheduling Problem (RCPSP). In the RCPSP, the goal is to determine a minimal makespan schedule subject to precedence and resource constraints. The generalization introduced in the RCPSP-PS is that, instead of executing all activities, only a subset of all activities has to be executed. We present a model that is based on two graphs: one representing precedence relations and one representing the activity selection structure. The latter defines which subset of activities has to be executed. Additionally, we present theoretical properties of this model and give an exact solution method that makes use of these properties by generating cutting planes and setting bounds on variables. Furthermore, three problem properties are introduced to classify problems in the literature. We compare our model to a model from literature on instances that possess a subset of these three problem properties and find a reduction in computing time. Furthermore, by comparing results on instances that possess all problem properties, it is shown that the computing times are decreased and better lower bounds are found by the cutting planes and variable bounds presented in this paper.

@en

Shared automated vehicles (SAV) are expected to benefit the sustainable development of urban regions and alleviate the negative impacts brought by the increasing number of private cars. In this paper, we envision a future scenario where non-pooled SAVs replace private cars and provide public on-demand mobility services to satisfy the mobility needs of a city's residents. To help service providers make profitable fleet sizing and management decisions, we develop a mixed-integer non-linear programming model that considers the congestion effects and the mode choice of urban travellers in different income classes, between SAVs and bicycles. Our model optimises both strategic decisions (fleet size, initial fleet distribution, and service quality level) and operational decisions (trip assignment, vehicle routing, parking, and relocation). Travellers’ preference for both transport modes is described through a binary logit model and congestion effects are described by dynamically varying travel times with respect to traffic flow in a non-linear fashion. In addition, we investigate two types of accept/reject mechanisms (mandatory vs. non-mandatory acceptance) which lead to an endogenously determined acceptance rate that can affect travellers’ willingness to use SAV services. The computational challenge posed by the non-linear and non-convex nature of the model is addressed through reformulation and the use of outer-inner approximation methods combined with a breakpoint generation algorithm. We demonstrate the effectiveness of our proposed method in a case study of the city of Delft in The Netherlands, as well as a scaling analysis on three toy networks with various sizes and demand profiles. A sensitivity analysis of key parameters is carried out to assess system performance. Computational results indicate that fleet sizing decisions are influenced not only by the population's geographical distribution and land use patterns but also by the pricing strategy, unit operating costs of the SAV fleet, network congestion level, and traveller behaviour. When the price rate of using SAVs is low, the fleet sizing decisions can also be influenced by the trip accept/reject mechanism and the travellers’ sensitivity to the service quality level. In addition, a low price of SAV service will attract more users but may not necessarily bring a higher profit because of the increased traffic congestion.

@en

The resource constrained project scheduling problem with a flexible project structure and consumption and production of resources, involves making a selection of activities and scheduling these activities in order to minimize the makespan, subject to precedence and resource constraints. Since finding a feasible selection of activities is NP-hard, we introduce the concept of group graphs and restrict ourselves to instances with an acyclic group graph. For these instances, which represent many practical cases, we show how to make a feasible selection of activities in polynomial time and use this concept to schedule the selected activities using a hybrid differential evolution algorithm. We compare this algorithm with an algorithm from the literature on special cases of instances without consumption and production of resources, and show that our algorithm creates solutions of higher quality. Furthermore, to compare general instances, we develop an ant colony optimization algorithm that performs slightly better on special cases than the algorithm from literature and show that the hybrid differential evolution algorithm outperforms the ant colony optimization algorithm on general instances.

@en

The Resource Constrained Project Scheduling Problem with a flexible Project Structure (RCPSP-PS) is a generalization of the Resource Constrained Project Scheduling Problem (RCPSP). The objective of the RCPSP-PS is to find a minimal makespan schedule subject to precedence and resource constraints, while only having to execute a subset of all activities. We present a general model, which is based on a precedence graph and a task selection graph. Furthermore, we introduce an exact solution method including procedures for generating cutting planes and variable reduction. It is shown that both the lower bound obtained from the linear relaxation, and the computation time needed to obtain integer solutions are improved using these procedures.@en

The era of intelligent transportation with automated vehicles (AVs) is coming. Nonetheless, the transition to this system will be a gradual process. On the one hand, some zones in the city may be dedicated to AVs with a fully intelligent traffic management system geared toward high performance. On the other hand, automated and conventional vehicles may have to be allowed to drive in the remaining zones of the urban network in a transition stage. In this paper, we consider a situation where AVs are deployed by a taxi operating company to serve door-to-door travel requests. Facing this transition period, a strategic flow-based vehicle routing model is developed to determine the optimal fleet size of automated and conventional taxis as a function of the gradually increasing coverage of the AVs-only dedicated area. Traffic congestion is considered through flow-dependent travel times. Two taxi company service regimes are tested: the User Preference Mode (UPM) and the System Profit Mode (SPM). In the UPM, passengers can choose their preferred vehicle type according to their preference. In the SPM, the taxi company will take charge of the vehicle assignment to maximize the system profit. The developed model formulations are applied to a case study of a large toy network. The results give insight into the performance of the heterogeneous taxi system on a hybrid network. Strategies are presented on how to adjust the fleet size of automated and conventional taxis to get the best system profit while satisfying the mobility demand. The SPM can bring more profit to the operating company by reducing the detour and relocation cost of taxis, reducing the salaries for drivers through a bigger fleet size of AVs, and reducing the delay penalty, compared to the UPM.

@en

Electric car-sharing systems have attracted large attention in recent years as a new business model for achieving both economic and environmental benefits in urban areas. Among different types, the one considered in this paper is the so-called one-way car-sharing system whereby a user can begin and end a trip at any station of the system. At the same time, the Vehicle-to-Grid (V2G) concept is emerging as a possible innovative solution for smart power grid control. A management system that combines car-sharing system operations and V2G technology is a recent challenge for academia and industry. In this work, a mixed integer linear programming formulation is proposed to find the optimal management of electric vehicles in a one-way car-sharing system integrated with V2G technology. The proposed mathematical model allows finding the optimal start-of-day electric vehicles distribution that maximizes the total revenue obtained from system users and V2G profits through daily electric vehicles charging/discharging schedules. These schedules are based on mean daily users' electric vehicles requests and electricity prices. The model can be applied to evaluate the possible average daily profitability of V2G operations. In order to test the model performance, we applied it to a small-size test network and a real-size test network (the Delft network in the Netherlands). Under the model assumptions, the adoption of V2G technology allows to fully cover the daily charging costs due to users’ trips and to obtain V2G profits by taking advantage of electric vehicles unused time without significantly reducing the satisfied car-sharing system demand. Most of the energy purchased to charge the electric vehicles batteries is provided back to the grid during energy peak load demand, creating benefits also for energy providers.

@en

Automated vehicles are becoming a reality. Expectations are that AVs will ultimately transform personal mobility from privately owned assets to on-demand services. This transformation will enhance the possibility of sharing trips, leading to shared AVs (SAVs). The preeminent aim of this paper is to lay foundations for fast and efficient algorithms to be used in such new driving conditions. These algorithms must be able to solve Dial-a-Ride problems with transfers (DARPT). Hence, they should efficiently assign passengers to vehicles and routes while also: administering vehicles dispatch, determining convenient parking for idling vehicles and managing vehicle routing in real-time. In this paper, we develop two integer linear programming models (one in continuous time and one in discrete time) and their extensions to solve the DARPT. Our models take into account routing, service times, constraints on maximum route time-span, unserved requests, preferred arrival and departure time, nonconstant travel times, convenient parking while optimizing routing costs and quality of the service. The models are tested on instances based on Google Maps data by solving them with a commercial solver. The results of these tests are the starting point for validating the performance of forthcoming, ad hoc metaheuristics to be used in real-life sized scenarios.@en

Short driving range, limited chargers, and long charging times challenge the profitability of electric taxi operations. In this paper, a charging algorithm is developed to accompany a taxi service with online trip requests, which uses a private charging infrastructure for both slow and fast charging. The vehicle charging curves are assumed to be piece-wise linear functions. The proposed algorithm uses historical operation data to generate a pro-active planning that avoids queuing of vehicles. The algorithm is built upon three sequential, iterative, finite-horizon Mixed Integer Linear Programs. This iterative process, in which the three MILPs are solved sequentially, allows the current time-step to be optimized, while taking future time-steps into account. This is achieved by optimizing over multiple time-steps, but only implementing the current time-step in each iteration. The sequential aspect of the algorithm allows the vast amount of information over time and space to be exploited for charging trip decisions in real time, while maintaining a tractable computation time. The first level with the longest horizon is an aggregated, daily problem, that plans the charging duration required for the fleet. The second level has a horizon of up-to three hours and is an aggregated, zone-based problem for determining charger selection and empty vehicle relocations. The third level translates the outputs of the first two problems to executable decisions for individual vehicles based on their real-time location, state of charge, and assigned passengers. The first level is the most computationally expensive and is solved using Column Generation. The performance of the first two levels is then independent of the fleet size, which makes the algorithm highly scalable. A case study with travel data for the city of Barcelona is used to test the model. Results show that the proposed method can utilize the full capacity of the charging infrastructure, and improve the number of accepted requests by 14% compared to employing a naive charging rule.@en

Combinatorial optimization (CO) problems are at the heart of both practical and theoretical research. Due to their complexity, many problems cannot be solved via exact methods in reasonable time; hence, we resort to heuristic solution methods. In recent years, machine learning (ML) has brought immense benefits in many research areas, including heuristic solution methods for CO problems. Among ML methods, reinforcement learning (RL) seems to be the most promising method to find good solutions for CO problems. In this work, we investigate an RL framework, whose agent is based on self-attention, to achieve solutions for the knapsack problem, which is a CO problem. Our algorithm finds close to optimal solutions for instances up to one hundred items, which leads to conjecture that RL and self-attention may be major building blocks for future state-of-the-art heuristics for other CO problems.

@en

Metaheuristics have been widely used to solve NP-hard problems, with excellent results. Among all NP-hard problems, the Travelling Salesman Problem (TSP) is potentially the most studied one. In this work, a variation of the TSP is considered; the main differences being, edges may have positive or negative costs and the objective is to return a Hamiltonian cycle with cost as close as possible to zero. This variation is called the balanced TSP (BTSP). To tackle this new problem, we present an adaptive variant of the iterated local search metaheuristic featuring also random restart. This algorithm was tested on the MESS2018 metaheuristic competition and achieved notable results, scoring the 5th position overall. In this paper, we detail all the components of the algorithm itself and present the best solutions identified. Even though this metaheuristic was tailored for the BTSP, with small modifications its structure can be applied to virtually any NP-hard problem. In particular, we introduce the uneven reward-and-punishment rule which is a powerful tool, applicable in many contexts where fast responses to dynamic changes are crucial.

@en

Emergency Medical Services organizations are responsible for providing paramedic crews, vehicles and equipment to transfer patients from one location to another in emergency and non-emergency settings. They must solve difficult scheduling and assignment problems to ensure on-time arrival of patients and the efficient use of health care resources during non-emergency operations. Ambulances can serve both emergency and non-emergency requests but are rarely available to serve non-emergency requests. Therefore, non-emergency requests are the responsibility of Patient Transfer Units. The objective of this study is to develop a mathematical model that will assign Patient Transfer Units to non-emergency patient transfer requests, design a schedule that will minimize travel costs and balance workloads and apply it to a real-world case study. This paper also proposes a framework to utilize historical patient transfer data in the scheduling process. The mathematical model provides decision support for the non-emergency patient transfer scheduling process.

@en

Surgery groups are clustered surgery procedure types that share comparable characteristics (e.g. expected duration). Scheduling OR blocks leaves many options for operational surgery scheduling and this increases the variation in usage of both the OR and downstream beds. Therefore, we schedule surgery groups to reduce the options for operational scheduling, ultimately bridging the gap between tactical and operational scheduling. We propose a single step mixed integer linear programming (MILP) approach that approximates the bed and OR usage and a simulated annealing approach. Both approaches are compared on a real-life data set and results show that the MILP performs best in terms of solution quality and computation time. Furthermore, the results show that our model may improve the OR utilization from 71% to 85% and decrease the bed usage variation from 53 beds to 11 beds compared to historical data. To show the potential and robustness of our model, we discuss several variants of the model requiring minor modifications. The use of surgery groups makes it easier to implementation our model in practice and, for operational planners, it is instantly clear where to schedule different types of surgery.

@en

The possibility of having driverless cars on the streets seems to be more real than ever. In this paper, we focus on developing exact methods that can determine the effects of privately owned automated vehicles (AVs) and how switching to those vehicles is going to change mobility in urban environments. The considered problem determines the routes of family owned AVs that minimize the transportation costs of that family while considering the possibility of using public transport as an alternative for some trips. We introduce a novel exact linear formulation for this problem which includes a linearized traffic congestion model and which is able to solve the user and system optimum variant of the problem to optimality. The introduced formulation can easily be adapted to consider the current situation with conventional vehicles and a situation where not only the travel time costs of the driver but also costs of the other passengers are taken into account. The main advantage of our novel formulation is that the optimal results can be obtained to explore potential changes of flows with vehicle automation in small networks. We investigated the behavior of the system, given the described scenarios, by applying our formulation to a case study.@en

Over the years, several ambulance location models have been discussed in the literature. Most of these models have been further developed to take more complicated situations into account. However, the existing standard models that are often used in case studies have never been compared computationally according to the criteria used in practice. In this paper, we compare several ambulance location models on coverage and response time criteria. In addition to four standard ambulance location models from the literature, we also present two models that focus on average and expected response times. The computational results show that the maximum expected covering location problem (MEXCLP) and the expected response time model (ERTM) perform the best over all considered criteria. However, as the computation times for ERTM are long, the average response time model (ARTM) could be a good alternative. Based on these results, we also propose four alternative models that combine the good coverage provided by MEXCLP and the quick response times provided by ARTM. All four considered models provide balanced solutions in terms of coverage and response times. However, the multiple response times target model (MRTTM) outperforms the other models based on computation time.

@en

The primary drivers for buying a ship from a certain yard are price, delivery time and quality. In order to decrease construction time and costs, shipbuilding companies are exploring the development of product-families to include family wide modularity and cross family standardization. Standardization is the use of identical components across multiple products, while modularity combines parts to create 'building-blocks'. This creates an opportunity for less inventory, a more efficient supply chain and shorter delivery times. Considering a network of suppliers and shipyards, the shipbuilder has to answer the following question: Which components and pre-assembled modules should be available in which inventory? Since the exact ship orders are not known, this can be seen as an optimization problem with uncertainty. To solve it, it is formulated as an integer linear program (ILP), and to handle the uncertainty, the Sampling Average Approximation (SAA) method is used. Several smaller instances are solved to optimality by Gurobi optimization software and the performance of this approach is evaluated along with the convergence of the SAA method. The results show convergence of the SAA method although only relatively small instances can be solved to optimality by the ILP.@en

Many ambulance providers operate both advanced life support (ALS) and basic life support (BLS) ambulances. Typically, only an ALS ambulance can respond to an emergency call, whereas non-urgent patient transportation requests can be served by either an ALS or a BLS ambulance. The total capacity of BLS ambulances is usually not enough to fulfill all non-urgent transportation requests. The remaining transportation requests then have to be performed by ALS ambulances, which reduces the coverage for emergency calls. We present a model that determines the routes for BLS ambulances while maximizing the remaining coverage by ALS ambulances. Different from the classical dial-a-ride problem, only one patient can be transported at a time, and not all requests are known in advance. Throughout the day, new requests arrive, and we present an online model to deal with these requests.

@en

In order to perform medical surgeries, hospitals keep large inventories of surgical instruments. These instruments need to be sterilized before each surgery. Typically the instruments are kept in trays. Multiple trays may be required for a single surgery, while a single tray may contain instruments that are required for multiple surgical procedures. The tray optimization problem (TOP) consists of three main decisions: (i) the assignment of instruments to trays, (ii) the assignment of trays to surgeries, and (iii) the number of trays to keep in inventory. The TOP decisions have to be made such that total operating costs are minimized and such that for every surgery sufficient instruments are available. This paper presents and evaluates several exact and heuristic solution methods for the TOP. We compare solution methods on computation time and solution quality. Moreover, we conduct simulations to evaluate the performance of the solutions in the long run. The novel methods that are provided are the first methods that are capable of solving instances of realistic size. The most promising method consists of a highly scalable advanced greedy algorithm. Our results indicate that the outcomes of this method are, on average, very close to the outcomes of the other methods investigated, while it may be easily applied by (large) hospitals. The findings are robust with respect to fluctuations in long term OR schedules.

@en

Background: Helicopter emergency medical services are important in many health care systems. Norway has a nationwide physician manned air ambulance service servicing a country with large geographical variations in population density and incident frequencies. The aim of the study was to compare optimal air ambulance base locations using both population and incident data. Methods: We used municipality population and incident data for Norway from 2015. The 428 municipalities had a median (5-95 percentile) of 4675 (940-36,264) inhabitants and 10 (2-38) incidents. Optimal helicopter base locations were estimated using the Maximal Covering Location Problem (MCLP) optimization model, exploring the number and location of bases needed to cover various fractions of the population for time thresholds 30 and 45 min, in green field scenarios and conditioned on the existing base structure. Results: The existing bases covered 96.90% of the population and 91.86% of the incidents for time threshold 45 min. Correlation between municipality population and incident frequencies was -0.0027, and optimal base locations varied markedly between the two data types, particularly when lowering the target time. The optimal solution using population density data put focus on the greater Oslo area, where one third of Norwegians live, while using incident data put focus on low population high incident areas, such as northern Norway and winter sport resorts. Conclusion: Using population density data as a proxy for incident frequency is not recommended, as the two data types lead to different optimal base locations. Lowering the target time increases the sensitivity to choice of data.

@en