Publications
Published
-
T. Raviv and M. Kaspi, The locomotive fleet fueling problem. Operations Research Letters, 40(1), 39-45, 2012.
-
M. Kaspi and T. Raviv, Service Oriented Line Planning and Timetabling for Passenger Trains. Transportation Science, 47(3), 295-311, 2013. (Israel railways instance)
-
M. Kaspi, T. Raviv and M. Tzur, Parking reservation policies in one-way vehicle sharing systems. Transportation Research Part B: Methodological, 62, 35-50, 2014.
-
M. Kaspi, T. Raviv, M. Tzur and H. Galili, Regulating vehicle sharing systems through parking reservation policies: Analysis and performance bounds. European Journal of Operational Research, 251(3), 969-987, 2016.
-
M. Kaspi, T. Raviv and M. Tzur, Detection of Unusable Bicycles in Bike-Sharing Systems. Omega, 65, 10-16, 2016.
-
M. Kaspi, T. Raviv and M. Tzur, Bike Sharing Systems: User Dissatisfaction in the Presence of Unusable Bicycles. IISE Transactions, 49(2), 144-158, 2017.
-
C. Bongiovanni, M. Kaspi and N. Geroliminis, The Electric Autonomous Dial-a-Ride Problem, Transportation Research Part B: Methodological, 122, 436-456, 2019.
-
M. Repoux, M. Kaspi, B. Boyaci and N. Geroliminis, Dynamic prediction-based relocation policies in one-way station-based car-sharing systems with complete journey reservations. Transportation Research Part B: Methodological, 130, 83-104, 2019.
-
M. Repoux, N. Geroliminis and M. Kaspi, Operational analysis of an innovative semi-autonomous on-demand transportation system. Transportation Research Part C: Emerging Technologies, 132, 103373, 2021.
-
M. Kaspi, T. Raviv and M. W. Ulmer, Directions for future research on urban mobility and city logistics. Networks, 2022.
-
C. Bongiovannia, M. Kaspi, J. Cordeau, and N. Geroliminis, A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations. Transportation Research Part E: Logistics and Transportation Review, 165, September 2022.
-
Y. Molenbruch, K. Braekers, O. Eisenhandler and M. Kaspi, The Electric Dial-a-Ride Problem on a Fixed Circuit. Transportation Science, vol 57, no 3, 594-612, 2023
-
Y. Eppel, M. Kaspi and A. Painsky, Decision Making for Basketball Clutch Shots: A Data Driven Approach. Journal of Sports Analytics, Pre-press, 1-16, 2023.
-
C. Bongiovannia, N. Geroliminis and M. Kaspi, A ride time-oriented scheduling algorithm for dial-a-ride problems. Computers & Operations Research, 164, May 2024.
Under Review
-
D. Schröder and M. Kaspi, Beyond the Price Tag: Quantifying the External Costs of Autonomous On-Demand Ride Pooling Services using Agent-Based Simulation Analysis.
-
O. Karny, D. Epstein and M. Kaspi, FASTER! Flexible Autonomous Shared Transit over Existing Rail.
-
Y. Shapira and M. Kaspi, A Column Generation Approach for Public Transit Enhanced Robotic Delivery Services.
-
N. Perel, E. Perel and M. Kaspi, The Israeli Queue with a Capacitated Server: Modeling and Approximations.
-
A. Shamir and M. Kaspi, A Reinforcement Learning Approach for Dynamic Lead Vehicle Routing in a Semi-Autonomous Last-Mile Transportation System.
The locomotive fleet fueling problem (2012)
This paper considers the problem of how to determine an optimal fueling schedule and contracting policy with fuel suppliers so as to minimize the total cost of the fueling operation. The problem is formulated as a mixed integer program and the formulation is enhanced by valid inequalities and domination rules. The enhanced model allows us to obtain near optimal solutions for large scale instances.
Service Oriented Line Planning and Timetabling for Passenger Trains (2013)
An integrated line planning and timetabling model is formulated with the objective of minimizing both user inconvenience and operational costs. User inconvenience is modeled as the total time passengers spend in a railway system, including waiting at origin and transfer stations. The model is solved using a cross-entropy metaheuristic. The line plan and timetable of Israel Railways is used as a benchmark. Using the same amount of resources, the average journey time of passengers is reduced by 20%.
Parking reservation policies in one-way vehicle sharing systems (2014)
In this study, we propose improving the performance of one-way vehicle sharing systems by incorporating parking reservation policies. In particular, we study a parking space reservation policy in which, upon rental, the users are required to state their destination and the system then reserves a parking space for them until they arrive at their destinations. We measure the performance of the vehicle sharing system by the total excess time users spend in the system. The excess time is defined as the difference between the actual journey time and the shortest possible travel time from the desired origin to the desired destination. A Markovian model of the system is formulated. Using this model, we prove that under realistic demand rates, this policy improves the performance of the system. This result is confirmed via a simulation study of a large real system, Tel-O-Fun, the bike-sharing system in Tel-Aviv. For all the tested demand scenarios, the parking reservation policy reduces the total excess time users spend in the system, with a relative reduction varying between 14% and 34%. Through the simulation we examine additional service-oriented performance measures and demonstrate that they all improve under the parking reservation policy.
Regulating vehicle sharing systems through parking reservation policies:
Analysis and performance bounds (2016)
We study the regulation of one-way station-based vehicle sharing systems through parking reservation policies. We measure the performance of these systems in terms of the total excess travel time of all users caused as a result of vehicle or parking space shortages. We devise mathematical programming based bounds on the total excess travel time of vehicle sharing systems under any passive regulation (i.e., policies that do not involve active vehicle relocation) and, in particular, under any parking space reservation policy. These bounds are compared to the performance of several partial parking reservation policies, a parking space overbooking policy and to the complete parking reservation (CPR) and no-reservation (NR) policies introduced in a previous paper. A detailed user behavior model for each policy is presented, and a discrete event simulation is used to evaluate the performance of the system under various settings. The analysis of two case studies of real-world systems shows the following: (1) a significant improvement of what can theoretically be achieved is obtained via the CPR policy; (2) the performances of the proposed partial reservation policies monotonically improve as more reservations are required; and (3) parking space overbooking is not likely to be beneficial. In conclusion, our results reinforce the effectiveness of the CPR policy and suggest that parking space reservations should be used in practice, even if only a small share of users are required to place reservations.
Detection of Unusable Bicycles in Bike-Sharing Systems (2016)
In bike-sharing systems, a small percentage of the bicycles become unusable every day. Currently, there is no reliable on-line information that indicates the usability of bicycles. We present a model that estimates the probability that a specific bicycle is unusable as well as the number of unusable bicycles in a station, based on available trip transaction data. Further on, we present some information based enhancements of the model and discuss an equivalent model for detecting locker failures.
Related Materials
Bike Sharing Systems: User Dissatisfaction in the Presence of Unusable Bicycles (2017)
In bike-sharing systems, at any given moment, a certain share of the bicycle fleet is unusable. This phenomenon may significantly affect the quality of service provided to the users. However, to date this matter has not received any attention in the literature. In this article, the users' quality of service is modeled in terms of their satisfaction from the system. We measure user dissatisfaction using a weighted sum of the expected shortages of bicycles and lockers at a single station. The shortages are evaluated as a function of the initial inventory of usable and unusable bicycles at the station. We analyze the convexity of the resulting bivariate function and propose an accurate method for fitting a convex polyhedral function to it. The fitted polyhedral function can later be used in linear optimization models for operational and strategic decision making in bike-sharing systems. Our numerical results demonstrate the significant effect of the presence of unusable bicycles on the level of user dissatisfaction. This emphasizes the need to have accurate real-time information regarding bicycle usability.
Related Materials
The Electric Autonomous Dial-a-Ride Problem (2019)
In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provides shared-ride services to users specifying their origin, destination, and preferred arrival time. Typically, the problem consists of finding minimum cost routes, satisfying operational constraints such as time-windows, origin-destination precedences, user maximum ride-times, and vehicle maximum route-durations. This paper presents a problem variant for the DARP which considers the use of electric autonomous vehicles (e-ADARP). The problem covers battery management, detours to charging stations, recharge times, and selection of destination depots, along with classic DARP features. The goal of the problem is to minimize a weighted objective function consisting of the total travel time of all vehicles and excess ride-time of the users. We formulate the problem as a 3-index and a 2-index mixed-integer-linear program and devise a branch-and-cut algorithm with new valid inequalities derived from e-ADARP properties. Computational experiments are performed on adapted benchmark instances from DARP literature and on instances based on real data from Uber Technologies Inc. Instances with up to 5 vehicles and 40 requests are solved to optimality.
Related Materials
Dynamic prediction-based relocation policies
in one-way station-based car-sharing systems with complete journey reservations (2019)
In this paper, we study the operations of a one-way station-based carsharing system implementing a complete journey reservation policy. We consider the percentage of served demand as a primary performance measure and analyze the effect of several dynamic staff-based relocation policies. Specifically, we introduce a new proactive relocation policy based on Markov chain dynamics that utilizes reservation information to better predict the future states of the stations. This policy is compared to a state-of-the art staff-based relocation policy and a centralistic relocation model assuming full knowledge of the demand. Numerical results from a real-world implementation and a simulation analysis demonstrate the positive impact of dynamic relocations and highlight the improvement in performance obtained with the proposed proactive relocation policy.
Operational analysis of an innovative semi-autonomous on-demand transportation system (2021)
Semi-autonomous transportation systems are an intermediate step towards full automation of transportation systems. They use and benefit from the technological advances brought by automation while being already implementable at larger scale under the current regulations and within the existing urban environment.
In this paper, we present a new type of semi-autonomous transportation system referred to as Multi-Layered Personal Transit System (MuLPeTS). It consists of convoys composed of one human-driven lead vehicle guiding several autonomous small capacity trailers in which the passengers travel. These trailers can detach from a convoy and travel autonomously in a protected environment before attaching later to another convoy. The interest of this transportation concept is threefold: (i) this assembly of vehicles is able and allowed to move in mixed-traffic conditions whereas fully autonomous driving is still largely restricted; (ii) a trailer can travel autonomously in the vicinity of stations to pick-up and drop-off passengers while the convoy it was previously part of continues its route without further delay; and (iii) passengers complete their entire journey on board a single trailer, that is they avoid the need to transfer. We analyze how this new type of transportation system relates to existing alternatives and propose an operational concept for it, in which we account for passenger assignment, lead vehicle routes and trailer movements, including empty trailer relocation. We extensively test this concept within a purpose-built simulation environment to evaluate the performance of this kind of system based on real-world data instances. The results highlight the most promising operational policies and characterize favorable system configurations.
Directions for future research on urban mobility and city logistics (2022)
This survey article provides an overview on future directions for research in urban mobility and city logistics. It sets a focus on three particularly serious changes in the business models: vehicle autonomy, crowdsourced logistics, and urban micro-consolidation centers. In the future, service fleets might fully or partially be autonomous which brings new operational opportunities and challenges. In many business models, crowdsourcing jobs are already common. While this might save costs, it also leads to uncertainty in the available workforce and their behavior. Finally, micro-consolidation centers enable the use of smaller, cheaper, and emission-friendlier vehicles, but lead to more complex planning and operations. For each topic, the article presents an overview on the relevant literature as well as important and open research challenges.
A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations (2022)
This paper contributes to the intersection of operations research and machine learning in the context of autonomous ridesharing. In this work, autonomous ridesharing operations are reproduced through an event-based simulation approach and are modeled as a sequence of static subproblems to be optimized. The optimization framework consists of a novel data-driven metaheuristic within a two phase approach. The first phase consists of a greedy insertion heuristic that assigns new online requests to vehicles. The second phase consists of a local-search based metaheuristic that iteratively revisits previously-made vehicle-trip assignments through intra- and inter-vehicle route exchanges. These exchanges are performed by selecting from a pool of destroy–repair operators using a machine learning approach that is trained offline on a large dataset composed of more than one and a half million examples of previously-solved autonomous ridesharing subproblems.
Computational results are performed on multiple dynamic instances extracted from real ridesharing data published by Uber Technologies Inc. Results show that the proposed machine learning-based optimization approach outperforms benchmark state-of-the-art data-driven metaheuristics by up to about nine percent, on average. Managerial insights highlight the correlation between selected vehicle routing features and the performance of the metaheuristics in the context of autonomous ridesharing operations.
The Electric Dial-a-Ride Problem on a Fixed Circuit (2023)
Shared mobility services involving electric autonomous shuttles have increasingly been implemented in recent years. Due to various restrictions, these services are currently offered on fixed circuits and operated with fixed schedules. This study introduces a service variant with flexible stopping patterns and schedules. Specifically, in the Electric Dial-a-Ride Problem on a Fixed Circuit (eDARP-FC), a fleet of capacitated electric shuttles operates on a given circuit, consisting of a recharging depot and a sequence of stations where users can be picked-up/dropped-off. The shuttles may perform multiple laps between which they may need to recharge. The goal of the problem is to determine the vehicles’ stopping sequences and schedules, including recharging plans, so as to minimize a weighted sum of the total user excess time and the total number of laps. The eDARP-FC is formulated as a non-standard lap-based MILP and is shown to be NP-Hard. Efficient polynomial time algorithms are devised for two special scheduling sub-problems. These algorithms and several heuristics are then applied as sub-routines within a Large Neighborhood Search metaheuristic. Experiments on instances derived from a real-life service demonstrate that the flexible service results in a 60%-85% decrease in the excess time at the same operational costs.
Related Materials
Decision Making for Basketball Clutch Shots: A Data Driven Approach (2023)
Decision-making is a crucial aspect for winning a basketball game. In particular, choosing the players who will take game-decisive shots (‘clutch shots’). While some coaches prefer the teams’ stars, others may prefer players who seemingly excel during clutch time (‘clutch players’) or are shooting well during a specific game (‘hot players’). In this study, we consider a variety of policies for choosing the shot-taker (for example, according to field goal percentage). Then, we compare the policies and rank them to create a policy hierarchy, which serves as a decision guide for the coach. We show that when our recommendations are implemented (i.e., the highest ranked player takes the shot) the success rate is significantly greater: 51.2%, compared to 41.3% in commonly taken clutch shots. Furthermore, our results indicate that players who excelled in past clutch shots are more likely to succeed, independently to their performance in the current game.
A ride time-oriented scheduling algorithm for dial-a-ride problems
This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theory, aims at finding minimal user ride time schedules in polynomial time. The algorithm can either return optimal feasible routes or it can return incorrect infeasibility declarations, on which feasibility can be recovered through a specifically-designed heuristic. The algorithm is furthermore supplemented by a battery management algorithm that can be used to determine charging decisions for electric and autonomous vehicle fleets. Timing solutions from the proposed scheduling algorithm are obtained on millions of routes extracted from DARP and e-ADARP benchmark instances. They are compared to those obtained from a linear program, as well as to popular scheduling procedures from the DARP literature. Results show that the proposed procedure outperforms state-of-the-art scheduling algorithms, both in terms of compute-efficiency and solution quality.
Beyond the Price Tag: Quantifying the External Costs of Autonomous On-Demand Ride Pooling Services using Agent-Based Simulation Analysis (under review)
Mobility On Demand (MOD) services, such as ride-pooling, have gained global popularity in providing on-demand transit services. By offering convenient and affordable trips, MOD services aim to attract users, reduce congestion, and alleviate parking demand in dense urban areas.
While prior research primarily focuses on operational costs and service measures, this study takes a broader perspective by considering the external costs associated with autonomous MOD ride-pooling services. Incorporating external costs into the design and evaluation of MOD services enables a comprehensive understanding of their impact on the entire urban population, informing effective regulations and incentives. A dynamic approach is proposed for calculating external costs, accounting for factors like air pollution, climate impact, noise and accidents. These costs are integrated into FleetPy, an agent-based simulation tool for ridesharing analysis and optimization.
A case study of Munich reveals tradeoffs between external costs, internal costs, and service quality. Results suggest mid-sized vehicles with three-person capacity strike a balance between energy efficiency and transport capacity. Optimized routing and pooling algorithms can significantly reduce external costs (up to 47%), although trip time may be affected due to speed-cost correlation. Considering external costs enables policymakers to formulate regulations supporting sustainable on-demand mobility. Continued research will advance understanding of external transportation costs, aiding the integration of autonomous on-demand mobility into urban transportation planning.
FASTER! Flexible Autonomous Shared Transit over Existing Rail (under review)
The environmental and safety benefits of shared, electric, autonomous vehicles remain unrealized due to technical challenges as well as regulatory and ethical concerns. The present focus on roadway deployment magnifies these difficulties. We propose synergizing current vehicle autonomy capabilities and existing urban rail infrastructure to create flexible, autonomous, shared transit over existing rail (FASTER). We develop queuing theory-based approximation and simulation models to represent the dynamics of such a service. Results for three rail systems in Boston show that during peak periods, FASTER achieves lower mean wait times and uses a third to half the energy required by traditional services. Off-peak, FASTER is far superior, permitting system managers to operate fewer vehicles without significantly affecting service quality. Thus, FASTER offers an immediate path to large scale shared autonomous transit services and the benefits they provide.
A Column Generation Approach
for Public Transit Enhanced Robotic Delivery Services (under review)
Autonomous Mobile Robots (AMRs) are small electric wheeled robots that travel at pedestrian speeds. In the last-mile service under consideration, a fleet of AMRs is distributed in multiple recharging depots within the service area from which they depart to provide point-to-point deliveries. We consider an operational scenario in which AMRs are allowed to travel onboard public transit vehicles, in order to extend the service range and reduce energy consumption. We propose two mixed integer linear pro-gramming formulations of the operational problem: arc-based and path-based. For the latter, we develop a column generation approach and a four-stage dynamic programming algorithm to solve the underlying sub-problem. Results for 700 problem instances with varying numbers of requests, robots, and public transit nodes indicate that while the arc-based formulation can only handle instances with up to 15 requests, the column generation approach can solve instances consisting of 150 requests in less than five minutes. A case study in a sub region of Tel Aviv demonstrates the ability of the proposed approach to handle larger instances based on real-world parameters. A sensitivity analysis further highlights the impact of the request time-windows width, the public transit capacity and the AMR’s battery range on the number of requests that can be served.
The Israeli Queue with a Capacitated Server:
Modeling and Approximations (under review)
The Israeli Queue is a batch service polling system in which a single server attends a collection of queues according to a seniority order. An arriving customer may belong to one of multiple classes. Upon arrival, she either joins a queue with customers from her class or opens a new queue in case she is the first in line from her class. Members of the class with the most senior customer are served together as a batch within a service time that is independent of their amount. This service regime is encountered in applications such as advanced elevator systems and on-demand shared mobility, where passengers with the same destinations may share a ride. However, in many systems, the vehicles' capacities are small and binding. Thus, calling for an implicit modeling investigating the Israeli Queue with a capacitated server (IQCS). In this paper, we introduce the IQCS model, in which only a limited number of customers can be served in a single service time. If the queue length of the served class exceeds the server's capacity, a capacity sized batch of customers is served and the seniority of the class is set according to its senior un-served customer. We approximate this system by formulating a corresponding quasi-birth-death process, and derive approximations for various performance measures. To validate our approach, we implement an ad-hoc simulation model and use it to compare the IQCS, the approximate model, and the Israeli Queue. Our analysis across various settings demonstrates the accuracy of the approximate model. Nonetheless, the presence of a remaining gap underscores the ongoing challenge of precisely and efficiently modeling the IQCS, posing an open question for the Operations Research community.
A Reinforcement Learning Approach for Dynamic Lead Vehicle Routing in a Semi-Autonomous Last-Mile Transportation System (under review)
In semiautonomous transportation systems, vehicle autonomy capabilities are utilized in a partial manner to adhere to current regulations. This study focuses on a personal transit system in which convoys composed of human-driven lead vehicles and several autonomous cabins provide station-to-station transportation. While the lead vehicles travel nonstop between the stations of the system, the cabins have the ability to detach from the convoys in the proximity of stations and autonomously travel in and out of the stations to pick-up and drop-off passengers. In a previous study, the assignment of passengers to cabins and the routing of the cabins were determined dynamically, while static circular routes were determined for the lead vehicles.
In this study, we examine the potential of dynamically shortcutting the routes of lead vehicles to better respond in real time to the current system state and the upcoming demand. We develop an approximate model of the system and formulated it as a Markov decision process (MDP). In particular, the MDP represents (1) the system state, i.e., the workload on each route; (2) an action, i.e., how many lead vehicles should shortcut each route; and (3) the reward, which is modeled as a penalty based on the number of cabins waiting to be served. Due to the so-called ‘curse of dimensionality’ in both the states and action spaces, the MDP cannot be solved straightforwardly. We develop an event-based simulation to represent the system’s dynamics and employ a reinforcement learning approach to implement good shortcut decisions dynamically.
We perform a numerical study based on a network consisting of 20 stations. We compare the shortcutting policy obtained using the reinforcement learning approach to the fixed lead vehicle routes proposed in a previous study, an improved fixed route policy and a rule-based dynamic shortcut policy. Compared to the base static lead vehicle route plan, the dynamic policy obtained by the reinforcement learning approach reduces the average cabin waiting times by 3.96 percent and the rule-based dynamic shortcut policy is capable of reducing the average cabin waiting time by 1.2 percent.