In this paper, we describe multi-itinerary optimization (MIO)—a novel Bing Maps service that automates the process of building itineraries for multiple agents while optimizing their routes to minimize travel time or distance. MIO can be used by organizations with a fleet of vehicles and drivers, mobile salesforce, or a team of personnel in the field, to maximize workforce efficiency. It supports a variety of constraints, such as service time windows, duration, priority, pickup and delivery dependencies, and vehicle capacity. MIO also considers traffic conditions between locations, resulting in algorithmic challenges at multiple levels (e.g., calculating time-dependent travel-time distance matrices at scale and scheduling services for multiple agents).
To support an end-to-end cloud service with turnaround times of a few seconds, our algorithm design targets a sweet spot between accuracy and performance. Toward that end, we build a scalable approach based on the ALNS metaheuristic. Our experiments show that accounting for traffic significantly improves solution quality: MIO finds efficient routes that avoid late arrivals, whereas traffic-agnostic approaches result in a 15% increase in the combined travel time and the lateness of an arrival. Furthermore, our approach generates itineraries with substantially higher quality than a cutting-edge heuristic (LKH), with faster running times for large instances.
Route planning and service dispatch operations are a time-consuming manual process for many businesses. This manual process rarely finds efficient solutions, especially ones that must account for traffic, service time windows, and other complicated real-world constraints. Additionally, scale becomes a challenge: service dispatch planning may involve multiple vehicles that need to be routed between numerous locations over periods of multiple days.
The development of large-scale Internet mapping services, such as Google and Bing Maps, creates an opportunity for solving route planning problems automatically, as a cloud service. Large amounts of data regarding geolocations, travel history, etc., are being stored in enterprise clouds and can in principle be exploited for deriving customized itineraries for multiple agents. The goal of such automation is to increase operation efficiency, by determining these itineraries faster (with less man-in-the-loop) and with better quality compared to manually produced schedules. However, multiple challenges must be solved to make this vision a reality.
No entries found