Field service booking, routing, and scheduling in a stochastic environment
Edison Avraham, Ph.D. student at the Department of Industrial Engineering
10 May 2022, 14:00 PM, Room 206& via zoom
Abstract:
The operation of field service systems requires booking service requests, characterized by location, desired service time windows, and duration of service. The accepted requests are assigned to mobile personnel that is later scheduled and routed accordingly. The steps in this process are subject to the stochasticity of the request’s arrival process, travel times, and service times. The travel times are also time-dependent and correlated. In this study, we present models and solution methods for the abovementioned steps. We refer to the members of the field service personnel as technicians, although the models and methods presented here may also apply to home attended deliveries, visiting nurses, etc. We first present a model for policy optimization of the online booking of technicians over a multiday horizon with a different cutoff for each day, where the goal is to maximize the expected ratio of accepted requests over time. Since the planning horizon is indefinite and the service horizon of each day overlaps the horizon of subsequent days, the objective is defined in terms of the steady-state performance. The interactions with the customers are performed in a single step: The system offers an assortment of time slots covering the next few days, and the user either chooses one of them or abandons the system. Upon the arrival of a service request, the provider estimates the opportunity cost of serving the request at each available time slot. The assortment of time slots offered following each service request is constructed by maximizing the expected net gain. The proposed method is benchmarked based on randomly generated datasets in various demand scenarios and geographies. The method outperforms more straightforward baseline policies common in practice significantly. Once the booking of requests for a single working day is completed, and the service tasks are assigned to technicians, the service provider faces the problem of routing and scheduling the operation of each mobile agent. This is a single-vehicle routing problem with stochastic service times, stochastic time-dependent travel times, and soft time windows, where the travel times may be interdependent. The objective is to minimize the expected route duration plus penalties for late arrivals. The stochasticity is modeled using a set of scenarios based on historical data. This approach captures the road network’s spatial and temporal interdependencies to be captured. We introduce a specialized branch-and-bound algorithm and a successful adaptive large neighborhood search heuristic for the problem. In a numerical experiment based on real historical travel time data, we demonstrate the applicability of both methods to problem instances of up to 40 customers and 40 scenarios. These dimensions are safe upper bounds for instances originating from the field service operation domain and may be marginally applicable in the context of home attended delivery. The resulting routes are tested on realistic scenarios not included in the problem input (the training set) to demonstrate the merits of using historical data. Our solutions are consistently superior compared with solutions that ignore the time dependency and/or stochasticity of the parameters. In the last part of the talk, we present an extension of the orienteering problem with stochastic and time-dependent travel and service times with soft time windows. A solution is a tour, determined before the vehicle departs from the depot. The objective is to maximize the sum of the collected prizes net of the expected penalty. We present an exact solution method for the problem based on a branch-and-bound algorithm enhanced by a local search procedure at the nodes. A numerical experiment demonstrates the merits of the proposed hybrid solution approach. The solution method to this problem can be used as a subroutine in a system that assigns tasks to technicians and routes them simultaneously.
Bio:
Edison Avraham graduated Magna cum Laude from the department of industrial engineering at Tel Aviv University in 2008. He completed his MSc study Magna cum Lauda in the department of industrial engineering at Tel Aviv University in 2014. He has been a Ph.D. candidate in the department since 2017. From 2008 to 2014, Edison served as an operational researcher in the IDF and was released at the rank of Captain. Edison has published three papers in Transportation Research Part B and won prizes for the best student paper at the national industrial engineering conference in 2017 and the ISTRC student conference in 2021. Edison worked as a developer and consultant in several organizations and is currently employed as an algorithm developer in Rafael.
