Commentary—Visualization in Vehicle Routing and Scheduling Problems

Abstract

Over the past 20 years, vehicle routing and scheduling has grown to be an important research area. Many papers have appeared in the literature, fundamental research questions have been answered, and new research areas have been developed. Also, vehicle routing and scheduling has grown to become an important application area. Successes have been documented, and commercial software systems have been developed. The domain of problems considered to be vehicle routing and scheduling has expanded. Microcomputers and geographic information systems have forced a reality and a practicality on commercially available routing and scheduling systems that were not envisioned in the 1970s. Prior to the microcomputer, vehicle routing and scheduling systems were primarily batch algorithms operating on a large mainframe computer. Since these systems did not possess significant graphics and interactive capabilities, their solution algorithms were forced to carry most of the burden for deriving a reasonable solution. The users of these systems had difficulty in “seeing” the solution and, therefore, they could not alter the system-generated solution manually. The vehicle routing and scheduling systems developed in the late 1970s were called computerized routing and scheduling systems . In the early 1980s, the first routing and scheduling systems on microcomputers were developed. These systems were slow computationally and contained weak algorithms. Some of these systems had reasonable graphics and user-intervention capabilities, while others had virtually no graphics. The first-generation systems were the forerunners of the microcomputer-based computer assisted vehicle routing and scheduling systems of today. The second-generation microcomputer-based vehicle routing and scheduling systems were developed in the mid 1980s. The commercial first- and second-generation systems cost between $1,000 and $150,000, and the types of problems they could solve were limited. Only a few of these packages survive today. Recently, the computer environment, along with the availability of digitized street network data, comprise two of the most impressive enhancements to building vehicle routing and scheduling systems. Visualization has become a key aspect in the development of these systems. When using a computer assisted vehicle routing and scheduling system, the user accepts the responsibility of finding a good solution and tailors the solution to suit current needs. The solution found in this manner is called the “user's solution” and, by definition, this solution is “good.” To achieve good solutions, the user demands high-quality graphics, excellent algorithms, detailed path generation capabilities, manual intervention capabilities, and a geographic information system. In his feature article, Chris Jones makes several references to vehicle routing and scheduling. The user's graphical ability to indicate starting points for vehicle routes demonstrates user input to an algorithm. A display of regions of stability for traveling salesman problem solutions illustrates the visualization of solution sensitivity. Chris Jones mentions an interactive approach to breaking cycles in a linear programming relaxation of a sequencing problem. In each of these examples, aspects of visualization in routing and scheduling are used. In this commentary, we present many other examples of the use of visualization in vehicle routing and scheduling. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.