Geo Map based VRP Solving
Real-world vehicle routing problems are usually very different from benchmarks problem. Firstly, in real-world application, each customer is based on a geo location measured in latitude and longitude. Secondly, a straight line cannot be assumed for the route from one customer to another. Instead, real traffic network and roads have to be considered when travelling from one customer to another.
The Vehicle Routing Scheduler Library makes it easy to consider these real-world vehicle routing problem scenarios including map based vehicle routing problem specification in which road and traffic network are considered when measuring the distance between depot and customers or customers to customers.
In this section, step-by-step tasks of solving geo map based VRP are described. For simplicity, Capacitated Vehicle Routing Problem (CVRP) is solved using various schedulers (i.e. solution methods).
- Go to Flavors section.
- Select GeoMap link of Capacitated Vehicle Routing Problem or Select Capacitated VRP → GeoMap menu as shown in Figure.
- CVRP GeoMap workspace will be launch as shown in Figure.
- Take note of the caption title: CVRP: Geo Instances(User-defined Map)(Clark & Wright Savings)
CVRP: Geo Instances: user is currently in CVRP GeoMap workspace
User-defined Map: default map
Clark & Wright Savings: default selected solution method
- Property accordion in Map Editor allows user to define problem constraints such as vehicle capacity and maximum route length, as well as the best known solution as shown in Figure above.
- Map accordion in Map Editor allows user to specify properties of the map as illustrated in Figure.
Properties of map are specified in Table.
|
Map Properties |
Description |
|
Can drag map |
Checked – user can hold down the mouse and drag the map |
|
Unchecked – the map will be fixed in position |
|
|
Show address on map location change |
Checked – whenever user drags the map around, the address of the pointer will be retrieved and display in Address text field |
|
Only available when Allow map tile and address to retrieved via internet is checked |
|
|
Allow map tile and address retrieved via internet |
Checked – the map will retrieve information such as address associated with a geo point on the map |
|
Internet connection should be available |
|
|
Show address in tooltip on mouse down |
Checked – address associated with the pointer will be displayed whenever mouse button is clicked |
|
Only available when Allow map tile and address to retrieved via internet is checked |
|
|
Use preloaded points and routes |
Checked – the map will use offline cache to prevent duplicated internet address geocoding or route retrieval |
|
It is not recommended to uncheck this feature because internet-based route retrievals are usually expensive |
|
|
Lat Rng |
It is used for offline cache features and should not be modified unless absolutely required |
|
Lon Rng |
It is used for offline cache features and should not be modified unless absolutely required |
|
Geo Location |
Latitude and longitude associated with the center of the map |
|
Address |
Address associated with the center of the map |
|
Go to Address button allows user to enter an address and automatically brings user to the location associated with the address on the map |
|
|
Zoom Level |
Current zoom level |
|
ZoomIn and ZoomOut buttons allow user to set current zoom level |
|
|
Map Mode |
It is used to control how the retrieved map tiles are maintained |
|
It is not recommended to change the default value of this feature for reducing internet traffic |
|
|
Map Type |
It is used to switch among different types of map (Satellite Map, Yahoo Map, Bing Map, Open Street Map, etc.) |
- For the purpose of reducing unnecessary internet traffic, uncheck Allow map tile and address retrieved via internet and Show address in tooltip on mouse down properties. And, check Use preloaded points and routes.
GeoMap workspace initially checks internet connection upon its first launch. This is to ensure that when there is no internet connection and no cache for the route between two customers, distance between two customers can be calculated based on geo distance (distance taking into account the curve of Earth). And when internet connection is available or caches for the route between customers are available, distance calculation is done by computing the actual travelled route distance between customers.