A Proposal and Analysis of New Realistic Sets of Benchmark Instances for Vehicle Routing Problems with Asymmetric Costs

Abstract

Despite their importance, relatively little attention has been paid to vehicle routing problems with asymmetric costs (ACVRPs), or their benchmark instances. Taking advantage of recent advances in map application programming interfaces (APIs) and shared spatial data, this paper proposes new realistic sets of ACVRP benchmark instances. The spatial data of urban distribution centers, postal hubs, large shopping malls, residential complexes, restaurant businesses and convenience stores are used. To create distance and time matrices, the T map API, one of the most frequently used real time path analysis and distance measurement tools in Korea, is used. This paper also analyzes some important issues prevailing in urban transportation environments. These include the challenges of accounting for the frequency and distance in which air travel differs from reality when measuring closeness, the differences in distance and time for outgoing and return trips, and the rough conversion ratios from air distance to road distance and to road time. This paper contributes to the research community by providing more realistic ACVRP benchmark instances that reflect urban transportation environments. In addition, the cost matrix analyses provide insights into the behaviors of urban road networks.

Keywords

• vehicle routing problems
• asymmetric costs
• benchmark instances
• urban transportation
• map application program interface
• road distance