Developing algorithmic solutions to improve the efficiency of staff routing assignments within the NYC Department of Environmental Protection
Written by Yuheng Wang
The Challenge
The New York City Department of Environmental Protection (DEP) plays a vital role in safeguarding the city’s water and air quality, managing waste, and leading environmental protection efforts. As part of its responsibilities, DEP inspectors conduct daily inspections of water and sewer connections at sites across the city’s five boroughs, based on requests from Licensed Master Plumbers. These inspection assignments are constantly changing, driven by the dynamic nature of ongoing construction projects. Each day presents a new and varied set of tasks, keeping the inspection schedule in constant flux.
Currently, the inspection process is entirely manual. Plumbers call the DEP to schedule inspection jobs, which are classified as either an 'AM job' (scheduled between 9 am and 1 pm) or a 'PM job' (scheduled between 1 pm and 5 pm). Each morning, before 9 am, a DEP staff member manually assigns inspection routes for around 10 inspectors, planning out roughly 60-70 jobs by plotting locations on a map, categorizing them by AM or PM, and designing routes based on personal experience.
This manual approach has drawbacks. First, the travel times are estimated based on human judgment, which often leads to inaccuracies when compared to actual travel conditions. Additionally, plumbers are required to wait at the job site for the full four-hour window without knowing the precise arrival time of the inspector. If plumbers leave before the inspector arrives, the job must be rescheduled. Lastly, inspectors frequently work overtime because the routes planned are not optimized, leading to inefficiencies and extended work hours.
The Project
To address these challenges with a more data-driven approach, the DEP is developing a new scheduling system. This system will allow plumbers to submit job requests electronically, and an algorithm will automatically generate optimized routes, which is a sequence of stops for each inspector. My summer project as a Siegel PiTech PhD Impact Fellow focuses on developing this routing algorithm.
After discussions with DEP staff, two key requirements emerged. The first is a more precise job schedule. Specifically, the DEP wants to transition from the current rigid AM/PM scheduling system to a more flexible appointment system that allows for precise scheduling. Second, they want the algorithm to incorporate traffic accident data to avoid areas with a high likelihood of accidents when generating the sequence of stops. By adopting this new system, the DEP aims to improve the accuracy of travel time estimates, reduce wait times for plumbers, and optimize inspectors' routes to prevent unnecessary overtime— all of which will contribute to a more efficient and effective inspection process across New York City.
The Proposed Solution
I approached this project by dividing the problem into two modules. The first module focuses on developing a prediction tool to estimate travel time between two locations within New York City. The second module addresses an optimization model to solve a so-called Vehicle Routing Problem with Time Windows (VRPTW).
For the first module, I implemented two different options to predict travel times. The first option utilizes Openrouteservice, a free, open-source routing service that provides route planning and travel time estimates. Openrouteservice is an excellent choice for a cost-effective solution. The second option leverages Google Maps, which incorporates real-time traffic data to provide highly accurate travel time predictions. In developing this module, I also took the traffic accident factor into account to compute the final travel time. Additionally, I designed an experiment to compare the performance of these two options. The results showed that, with the proper setup of the optimization algorithm (which will be introduced in the 'second module' shortly), Openrouteservice provides a sufficiently acceptable route for practical implementation.
For the second module, I used Google OR-Tools, a powerful optimization toolkit developed by Google that incorporates state-of-the-art algorithms to solve vehicle routing problems. OR-Tools is highly versatile and adept at handling complex constraints, making it particularly well-suited for tackling VRPTW. Utilizing OR-Tools, I identified an optimized routing schedule that minimizes travel time, ensures that all jobs are completed within their designated time windows and scheduled at the earliest possible time.
In addition to optimizing for time windows, the algorithm takes several other factors into account to further enhance the scheduling process. For instance, it automatically incorporates a 30-minute lunch break for each inspector, ensuring compliance with labor regulations and providing rest for the workers. The module also considers additional constraints, such as assigning specific inspectors to jobs that require unique expertise or certification. Furthermore, it can accommodate varying starting locations for inspectors, enabling them to begin their routes from different points across the city rather than just the DEP office. This flexibility helps reduce travel times and ensures a more efficient distribution of resources, making the entire inspection process more streamlined and responsive to the real-world dynamics of New York City.
The following image illustrates a potential output for one of the optimized routes. This visualization includes a detailed summary of each job, displaying the sequence in which they are to be completed and the estimated arrival times for each location.
Future Steps
Since this scheduling system and algorithm are being implemented for the first time at the DEP, there are many unknowns and exciting new challenges to consider as the project develops. Below are some intriguing questions and potential future steps that we discussed:
Optimize with better prediction of inspection time: Currently, we default inspection times to 30 minutes, though different job types actually require varying durations. Incorporating the variability would greatly enhance route reliability. Additionally, accounting for the varying skill levels of inspectors on different job types would be a valuable and interesting extension to the system.
Developing the Scheduling System: Although the scheduling system and optimization algorithm are currently being developed as separate components, in practice, they are deeply interconnected. Integrating these two elements can significantly enhance overall performance. Aligning schedules with optimized routes would potentially reduce travel times and improve the accuracy of arrival time predictions.