A Heuristic Approach for GPS-Based Routing

Introduction

Vehicle routing is an important challenge for many organizations with widespread applications. A familiar example is package deliveries from warehouses to homes, where vehicles must traverse the infrastructure of an established road network to visit multiple destinations to deliver packages. (Or pick up packages, or provide a service, etc.) This can be at the scale of a city (as is common for Amazon.com) or at the scale of a state, country, or continent (as is common in less-than-truckload freight). The operations manager must identify a routing for each vehicle, such that every destination is visited with minimum total driving time. (Alternative objectives are to minimize distance or carbon emissions. In this paper, we use driving time as the objective.) In many settings, this needs to be done on daily basis, for an ever-changing list of destinations.

The manager must address three distinct issues:

• 1)

  which of multiple vehicles to assign to visit which of multiple destinations;

• 2)

  the best set of road links to traverse between each destination pair (the well-known “shortest path problem” in the operations research literature); and

• 3)

  the order in which each vehicle visits its respective destinations (the famous “traveling salesman problem”).

This “multiple-vehicle routing problem” is referred to as the MVRP. A key building-block is the single-vehicle routing problem (SVRP), which is also known as the Traveling Salesman Problem.

Vehicle routing problems are combinatoric in nature and thus computationally very challenging. Practical vehicle routing problems have the additional complexity of traffic congestion during peak times of the day. Thus, in practice, vehicle routing problems are generally addressed using heuristics rather than solving to optimality.

The MVRP can be formulated as a 0-1 optimization model. After the necessary data (which can be voluminous) are acquired and pre-processed, the model can be solved using optimization software to identify the best routing for every vehicle. However, before the model can be solved, it is necessary to determine driving times between every pair of locations. in addition to the problem of gathering this voluminous data, there are two other practical challenges to using the formal optimization approach to address the MVRP. First, solutions times can be prohibitive, and second, specialist personnel are required. We discuss each in turn.

Technically, the SVRP and MVRP fall into the class of “NP-hard” problems, which means that problem scales up brutally. In practice, solution times to find the exact solution can be hours, days or more even with the fastest computers. As a practical matter, obtaining an optimal solution too late to use is worthless. Thus, there is a need to able to identify “good” feasible solution in time to employ them. Therefore, heuristics must be used when results are required quickly, or for larger problems. In this paper we show how to use The Excel Solver with a heuristic solving method to obtain a good solution quickly.

An ordinary manager cannot be expected to have the OR expertise needed to solve an MVRP. The data acquisition and pre-processing required to initiate the MVRP are time-consuming and require a high level of analytical skill. Once data acquisition is accomplished, and the shortest paths are determined (each with their own technical challenges), the ability to formulate the MVRP and access and run the optimization software requires additional advanced analytical skill. This requires expertise from operations research professionals (employees or consultants). Obviously, many small and medium companies which must plan deliveries and pickups from customers and vendors cannot afford the O.R. professionals needed to support the software for finding solutions. Thus, they cannot in practice use optimization models or dedicated software to solve such routing problems.

In order to accommodate traffic congestion, the road network used by the MVRP can be extended to establish, for each physical road link, a set of corresponding time-of-day links, each with its own time-of-day-dependent travel time. Additional constraints ensure that the correct time-of-day link is used. This requires additional technical know-how by specialist personnel. It also increases problem size and combinatoric complexity, further increasing computational burden and solution time. Thus, there is a need for approaches that generate “good” solutions to the MVRP with time-of-day congestion, quickly and cheaply.