Decision support system for solving the street routing problem

Abstract

Servicing a large number of customers in a city zone is often a considerable part of many logistics chains. The capacity of one delivery vehicle is limited, but, at the same time, it usually serves plenty of customers. This problem is often called a Street Routing Problem (SRP). Key differences between Vehicle Routing Problem (VRP) and SRP are presented here. The main problem of SRP is that when the number of customers is huge, the number of delivery path combinations becomes enormous. As the experimental results show in the case of SRP the error on the length of delivery routes based on an expert's judgment when compared to the optimal solution is in the range of 10–25%. As presented in the paper, only using decision support systems such as Geographical Information Systems (GIS) makes possible to effectively manage SRP. Besides classical measurements used in VRP, such as total length of routes or time required for delivery in each route, other measurements, mostly qualitative ones, are presented. All of these are named as visual attractiveness. This paper discusses possible relationships between quantitative and qualitative measurements that give a promise for finding better solutions of SRP. Several new types of heuristics for solving SRP are evaluated and afterward compared using the real data. One of the key properties of GIS to use routing software is its flexible interactive and user‐friendly environment. Routing software can find a good solution and explore the possibilities while an expert later can change the calculated routes to explore other possibilities based on the expert's judgment. This paper presents a practical use of new heuristics with the ArcView and solution of address mail for several cities in Slovakia served by Slovak Post ltd. Other Decision Support Systems that solve SRP are presented as TRANSCAD developed by Caliper Corporation or GeoRoute promoted by Canadian Post and GIRO.

First published online: 27 Oct 2010

Keyword : SRP, VRP, decision support system, GIS, heuristics, visual attractiveness