Logistics and transportation decision support systems rely on models of travel distance for evaluating scenarios and estimating costs. This paper presents a new method to model travel distances that combines the accuracy of shortest path travel with the simplicity of a distance approximation. The distance approximation was developed and tested in a geographic information system (GIS)-based decision support system for snow removal and disposal in Montreal, Canada.