Maptitude Help / Routing, Directions, and GPS / Vehicle Routing

Solving a Vehicle Routing Problem

Many businesses and government agencies transport goods from one or more central locations to a set of destinations. It is important to manage these operations efficiently, both to reduce operating costs and to ensure that pickups and deliveries adhere to reasonable service standards.

This general problem is known as the vehicle routing problem. Solving the vehicle routing problem involves determining which vehicles are required to service the destinations, and developing a route and schedule for each one. Because there are many variations of the problem, it can be very difficult to solve. Maptitude provides a rich set of vehicle routing tools that solve various types of routing problems.

The best way to introduce the vehicle routing problem is to give an example. Imagine a company that has one warehouse that supplies goods to 20 retail stores in various locations, as shown in the map below.

Each day, trucks must deliver goods from the warehouse to each of the retail stores, and then return to the warehouse. Each depot has a fixed number of trucks, and each truck has a fixed capacity, which is a limit on the weight or volume of the goods that the truck can carry. Each retail store has some demand, which is the weight or volume of goods that must be delivered each day. In the simplest version of the vehicle routing problem, the company must determine the number of trucks that are needed to meet the demand at each store, and find cost-efficient routes for each truck.

The starting points for each route (such as the warehouse in the above example) are known as depots, and the points to be visited are known as stops. A vehicle route starts at a depot, visits one or more stops, and may or may not return to the depot.

The goal of the procedure is to obtain a set of routes that optimize the total time spent by the entire fleet of vehicles. The procedure considers the number of vehicles of various capacities and the cost to operate them when determining a solution.

There are many factors that can make a vehicle routing problem more complex. The list below shows some common situations by the procedure:

• There may be more than one depot location, and stops can be serviced by trucks from anyone of these depots. This kind of a problem is known as a multiple-depot problem.
• There may be time restrictions on when deliveries can be made to some or all of the stops. For example, a particular stop might require that goods be delivered between 5:00AM and 7:00AM, before it opens at 8:00AM. This type of restriction is known as a time window. In addition, the whole operation may last more than one day, which is called multiple-day operation.
• Each stop may require a certain amount of time to service. In most cases, each stop has a fixed service time that is independent of demand. For example, it takes time to pull a truck into a loading dock and check in with the receiver. There is also a per-unit service time that depends upon the demand at that stop. For example, the time it takes to move boxes from the truck onto the loading dock varies depending on how many boxes there are to move.
• There may be a time restriction on total route length, or route duration. For example, when delivering take-out food, it may be desirable that the full route length is not more than an hour.
• There may be a restriction on the number of trips that each vehicle can make during the whole operation, which lasts either one day or multiple days.
• There may be backhaul stops. For example, vehicles may need to pick up empty containers at the end of their delivery trip. Backhaul stops can only be visited after all delivery stops are visited in a route.
• A vehicle route may contain mixed pickup and delivery stops, where the pickups and deliveries do not need to correspond to each other. A stop may require either a pickup, a delivery, or both services. These routes may also require a certain amount of shuffling space for the driver to be able to access delivery goods as the vehicle fills up with pickup goods and a maximum initial load which is the percent of space allotted for the delivery goods in a vehicle when it departs from the depot.
• You may want to offload the vehicles at the last stop before returning to the depot.
• You may want to minimize the number of routes. If a stop requires a longer waiting time due to its late opening time, the procedure may determine that overall time can be saved by dispatching another route to service the stop later. When you choose to minimize the number of routes, the procedure may choose to have a vehicle idle longer to service that same stop. The overall total time spent by the fleet will likely be higher than without minimizing the number of routes, but the number of routes will be lower.
• Vehicle routes may use a driving schedule, which includes different types of breaks, such as noon breaks, automatic rest breaks, and night breaks. Noon breaks have a higher priority over automatic rest breaks.
• A route may not need to end at the depot. In other words, the route does not contain the return trip from the last stop to the depot. This is often referred as an open-ended route instead of a closed tour. For example, a driver may want to drive home directly from the last stop of the day instead of returning to the depot. Another example is when the route duration constraint is effective only to the point of the last stop, such as in fresh goods delivery services.
• There may be a need to balance the routes based on the number of stops, the distance traveled, the total time traveled, the total cost, or the total loaded weight/volume. When doing route balancing, the overall time spent by the entire fleet of vehicles will likely be higher than without balancing.

When building routes without balancing between them, after creating a route, different ways of ordering the stops are tested within a route to improve the solution. When building routes with balancing, in addition to testing ordering stops differently within each route, swapping stops between routes is tested in an attempt to balance routes. Therefore, more solutions are checked, which could lead to a better solution.

The vehicle routing problem uses general-purpose methods that are appropriate for a fairly broad class of problems. There are some variations of the vehicle routing problem not handled directly within the Routing Deliveries & Pickups Wizard. Here are a few examples:

• Mixed products – Several different products must be delivered in the same vehicle, but some vehicles have restrictions on the goods that can be carried
• Partially pre-ordered routes – Certain stops must be visited in an exact order
• Other constraints – There are work rules or regulations that impose other types of constraints on the routes to be developed

Custom solutions for many of these variations on the vehicle routing problem are available from Caliper Corporation. In addition, the general-purpose methods that are included with Maptitude can be modified to handle special restrictions or to improve performance for some types of problems. Please contact Caliper Corporation for more information.

Preparing Data for Vehicle Routing

The Routing Deliveries & Pickups Wizard requires the following:

• A point layer with the location of depots (the “depot layer”) that includes the times that vehicles can be dispatched. Optionally, if you will want to offload the contents of vehicles at a location before returning the empty vehicles to a depot, you will need a selection set of depots and a selection set of offload locations in the depot layer.
• A point layer with the location of stops (the “stop layer”) that includes the times that the stops can be serviced, the unit demand, and both service and per-unit times.
• Information on the availability of vehicles, their capacity, their weight limits, and their cost at each depot. This can be in a table (the “vehicle table”) or entered and saved when using the Vehicle Routing procedure.

Depot and Stop Layers

To solve a vehicle routing problem, you must first prepare layers that contain the point locations of the depots and stops. The depots and stops can be either in the same layer, or in different layers.

If you use a single layer for both depots and stops, or if your layers contain extra points other than stops and depots, you must create a depot selection set and a stop selection set. You can create selection sets of stops and depots using any of the Maptitude selection commands and tools. For more information on selection sets, see Filters, Queries, and Selection Sets.

If you already have a point layer or layers for the depots and stops but some of the required fields are missing, you can add them using the Dataview>Table>Modify command, or create a joined view using the Dataview>Table>Join command. For more information, see Working with Tables, Databases, & Charts and Joining Your Data to a Map. Alternatively, you can specify fixed values for Open Time, Close Time, Service Time, Per Unit Time, Delivery Demand, and Pickup Demand in the Routing Deliveries & Pickups Wizard without having to modify your layers.

You may specify additional fields that you want included in the vehicle reports (e.g., address, contact name, drop-off instructions).

Time Windows

In both the depot and the stop layers, the Open Time and Close Time fields use 24:00 format, so 8:30AM should be written as 830, while 6:30PM should be written as 1830. A stop can also have multiple time windows. For example, a stop may accept deliveries from 10:00AM to noon and again from 2PM to 5PM. In this case, you will need separate fields in the stop layer for each of the time windows (e.g., OpenTime1, CloseTime1, OpenTime2, CloseTime2). Depots, on the other hand, have only one time window.

The opening and closing times of time windows must obey the following rules:

• The length of a time window must be greater than zero
• The opening times and closing times across all time windows must be in ascending order
• There must be no time overlapping between any time windows
• Only the closing time of last time window can cross midnight and span into the next day
• The closing time of a time window that crosses midnight must be less than the opening time of the first time window, namely, the accumulated time span across all the time windows must be less than a day

A multiple-day operation must be used for the after-midnight section of a time window to take effect. If the closing time of the last window exceeds midnight, it will be cut short at the midnight that is the end of operation. Here are some examples:

In general, as the time windows become more and more restrictive, the number of vehicle trips that are required to service the stops increases. If you do not need time window restrictions, you can simply set the open time to 0 and the close time to 2400.

Service Times

Vehicle routing accounts for the time required to service each stop when calculating routes. The service time can have a fixed component and a variable component that is demand dependent (time per unit). Both of these components can vary from stop to stop. The fixed time, for example, at one stop may take longer if it is difficult to park there or if it lacks a loading dock. Likewise, the per-unit time may be longer at a stop that requires delivery to an upper floor.

The amount of time it takes to service a stop is as follows:

service time = (fixed time) + (number of units) * (time per unit)

NOTE: Certain combinations of time windows and service times may make it infeasible to service some stops.

Vehicle Data

Vehicle information can be entered manually while performing vehicle routing or imported from a vehicle table. For each depot, you must specify the types of vehicles available. For each vehicle type, you must specify:

• The ID of the depot to which the vehicle type belongs
• A unique name for the vehicle type, such as "Truck X," "Vehicle Y," etc.
• The number of vehicles for the vehicle type
• The capacity of the vehicle type, the unit of which must match the unit of demand at the stops
• The purchase/operating/rental cost

The following field is optional and only required if your vehicles have maximum weight restrictions:

• Maximum Weight

For reporting purposes, each vehicle type defined can only be used by one depot.

If you are importing the vehicle information from a table, it must contain the following fields

NOTE: The vehicle cost specified above is only one of the trip cost components. The other cost components include the cost for driving distance, the waiting cost, and the cost for trip breaks. The total trip cost is the sum of all these four cost components.

Using the Routing Deliveries & Pickups Wizard to Solve a Vehicle Routing Problem

The Routing Deliveries & Pickups Wizard solves complex routing problems with time window, heterogeneous fleet, backhaul, mixed pickup and delivery, and route length constraints. It can handle multiple depots and open-ended routing problems. Additionally, you can choose to balance routes based on any of five different criteria: time, distance, cost, load volume, or the number of stops.

In addition, if some stops are not visited due to any restriction (such as vehicle capacity or time windows), a selection set named “Unserviced” will be created on the stop layer.

   To Solve the Vehicle Routing Problem

1. Open a workspace with a map that contains a depot layer and a stop layer.
2. Choose Tools>Routing & Directions>Routing Deliveries & Pickups or click  Routing Deliveries & Pickups in the analysis tools drop-down on the Standard toolbar to start the Routing Deliveries & Pickups Wizard.
   
3. Choose the Create New Vehicle Routes option from the radio list. You can start with settings from a previous configuration by choosing it in the Copy Settings From drop-down list or choose None to leave the route settings blank.
4. From the Operation Mode drop-down list, make choices as follows:

5. If your stop layer contains records with multiple time windows, specify the maximum number of time windows.
6. If you are planning a multiple-day routing operation, specify the number of operation days. The maximum number is 30. Any number greater than one means it is a multiple-day operation.
7. Enter a maximum computing time in hours. The process will stop after it has reached this maximum computing time and return routes that may not be balanced or the most optimized.
8. Click Next> to specify information about the stops. Make choices as follows:
   

TIP: You can choose Fixed Value to set a value to use for all stops for demand, service time, per unit service time, open time, close time, and weight per unit.

9. Click Next> to specify information about the depots. Make choices as follows:
   

TIP: You can choose Fixed Value to set a value to use for all depots for open time, and close time.

10. Click Next> to specify information about the vehicles.
11. To manually specify the available vehicles, click to add a vehicle type.
    
    If you have a vehicle table, click , choose a file type, browse for the table, and click Open to display the Load Vehicle Table dialog box. Verify that the correct fields are chosen for Depot ID, Vehicle Type, Cost, Number of Vehicles, and Capacity, and click OK.
12. For each vehicle type that you add, make choices as follows:
    

• Choose the depot to which the vehicle belongs from the drop-down list in the Depot column
• Enter a vehicle type in the Vehicle Type column
• Enter the number of vehicles of the vehicle type in the Vehicle Count column
• Enter the purchase/operating/rental cost in the Cost column
• Enter the capacity of the vehicle type in the Capacity column, using the same units as stop layer demand
• Optionally, enter the maximum weight limit in the Max Weight column, using the same units as stop layer weight per unit

Repeat steps 11 and 12 until you have defined all of the vehicle types available at each depot.

13. Click Next> to specify the driving schedule and trip cost. Make choices about the scheduling options and trip cost parameters as follows:
    

To do this...	Do this...
Specify the earliest and latest driving time	Check the box in the Driving starting at row and specify the start and end times in the Value column.
Specify a midday break	Check the box in the Noon break starting at row and specify the start time and duration in the Value column.
Specify automatic rests	Check the box in the Automatic rest duration row and specify the duration and interval, choose whether to base the rest break interval on total route time or based on accumulated driving time, and enter a flexibility time interval. If an automatic rest break occurs within the time flexibility interval of the drive-time window or a noon break, the break is ignored.
Specify cost of driving distance	Enter a dollar amount for the operational cost of each mile traveled.
Specify waiting cost	Enter a dollar amount for each hour spent waiting at stops as well as waiting-caused inconveniences
Specify automatic rests	Enter a dollar amount for each hour spent in mandatory breaks along the trip.
Adjust speeds for the street layer	Click Driving Speeds, enteruse the sliders to make the speeds faster or slower for the different road classes or enter target speeds for some different road classes, and click OK.The sliders correspond to speeds factors 1/5, 1/3, 1/2, 1, 1.176, 1.538, and 2.
Exclude travel on some links	Click Exclude Links and check the All Ferries box to exclude traveling on ferries and/or check the Selected Links box and choose a selection set that contains the links to exclude from the Selection Set drop-down list. Click OK when you are done.

14. Click Next> to specify additional options for the procedure. Make choices as follows:
    

To do this...	Do this...
Modify the title or description	Edit the text in the respective boxes
Have vehicles return to the depot	Check the box in the Vehicles return to depot row.
Use all available vehicles	Check the box in the Use All Vehicles row. This may result in shorter routes with less capacity than specified in vehicle settings.
Minimize the number of vehicle trips used	Check the box in the Minimize Number of Routes row. If a stop requires a longer waiting time due to its late opening time, the procedure may determine that overall time can be saved by dispatching another route to service the stop later. When you choose to minimize the number of routes, the procedure may choose to have a vehicle idle longer to service that same stop. The overall time spent by the entire fleet of vehicles will likely be higher when minimizing the number of routes.
Specify the maximum number of trips a vehicle can make	Check the box in the Maximum # of Routes per Vehicle row and enter a number in the Value column.
Specify the maximum allowed time of a vehicle trip	Check the box in the Maximum Route Time Duration row and enter a number in the Value column.
Specify the shuffling space and departure load for mixed pickup and delivery trips	Enter percentages in the Value column for the minimum percentage of space for when pickup and delivery are done at each stop in the Minimum Shuffling Space row and for the departure load in the Maximum Initial Load row.
Balance the routes	Check the box in the Balance Routes by row, choose whether to balance the route by time, distance, cost, load, weight, or number of stops from the drop-down list in the Value column, specify the route balance difference tolerance in the Balanced routes can differ by row, and choose whether to balance the routes within each depot or across every route from the drop-down list in the Balance row. The overall time spent by the entire fleet of vehicles will likely be higher than without balancing.
Limit the stops to the direction of travel on a street	Check the box in the Conduct same-side service row and choose whether to use stops on the right side or left side from the drop-down list in the Value column. Also enter a maximum distance from the road centerline for a stop to be considered. NOTE: Stops on one-way streets must be on the chosen side to use this option or the procedure will return an error.
Minimize vehicle idle time	Check the box in the Minimize Vehicle Idle Time row so that total trip time includes vehicle idle time, which is the time a vehicle waits at a depot before a trip begins. This option will attempt to minimize total trip time across all trips.
Prohibit U-Turns	Check the box in the Prohibit U-Turns row.

15. Click Finish.

Maptitude solves the vehicle routing procedure, displays the routes on the map, and opens the Routing Deliveries & Pickups Manager.

   To View Details About One or More Routes

1. You can view details about routes, display a map of a single route, and create reports with detailed information about the routes using tools in the Routing Deliveries & Pickups Manager as follows:
   

2. If your routes include any rest, lunch, or night breaks you can check the Show Breaks box in the Edit Schedules drop-down to see the breaks in the list of stops for a route or uncheck it to omit breaks from the list of stops.
   

   To Load Existing Routes onto a Map

1. Open a map that contains a depot layer and a stop layer.
2. Choose Tools>Routing & Directions>Routing Deliveries & Pickups or click  Routing Deliveries & Pickups in the analysis tools drop-down on the Standard toolbar to start the Routing Deliveries & Pickups Wizard.
3. Choose the Load Existing Vehicle Routes option from the radio list.
4. Choose a route from the drop-down list or choose Load config file, browse for the Vehicle Routing Configuration file (.VRPConfig), and click Open.
5. Click Next to display the Stops page.
6. The stop layer and fields are loaded from the previous run of the procedure. Make any changes and click Next to display the Depots page.
7. The depot layer and fields are loaded from the previous run of the procedure. Make any changes and click Next to display the Vehicles page.
8. The vehicles used from the previous run of the procedure are displayed. Make any changes to the vehicles and click Next.
9. The options used from the previous run of the procedure are displayed. Make any changes to the options and click Finish.

Vehicle Routing Results

The Customer-Routes dataview will contain the following fields:

Editing Vehicle Routes

Once you have created vehicle routes, you can use the Routing Deliveries & Pickups Manager to modify routes. You can change the color and name of a route, modify the route settings, move stops, and delete routes.

Sometimes there will be stops that were not assigned to any route in the initial solution, or that are removed from routes by you. The Routing Deliveries & Pickups Manager lets you handle these unserviced stops in several ways:

• You can modify the settings that were used to produce the routes and rerun the procedure. For example, you could modify the number of trucks available or change the balancing method, then rerun the procedure to see if there are fewer unserviced stops.
• You can use the tools to manually move stops from one route to another, add unserviced stops to a route, or remove stops from a route. Changes you make to the routes are automatically updated on the map and in the Routing Deliveries & Pickups Manager. These tools are accessible via a drop-down list in the Vehicle Routing Manager:
  

To Change the Style of a Route or a Route Name

1. Click on the style sample next to the route to display the Route Settings dialog box.
2. Enter a Name in the Route Name edit box and choose a line style, width, color, and opacity for the route.
3. Click OK.

To Modify the Stops Serviced

1. Click  to display the Stops portion of the Vehicle Routing Wizard.
2. Make any changes to the stops, such as the layer and/or selection set to use, and click OK.
3. Click to run the vehicle routing procedure again with the changes to the stops.

To Modify the Depots Serviced

1. Click  to display the Depots portion of the Vehicle Routing Wizard.
2. Make any changes to the depots, such as the layer and/or selection set to use, and click OK.
3. Click to run the vehicle routing procedure again with the changes to the depots.

To Modify the Available Vehicles

1. Click  to display the Vehicles portion of the Vehicle Routing Wizard.
2. Make any changes to the vehicles available at each depot and click OK.
3. Click to run the vehicle routing procedure again with the changes to the vehicles.

To Modify the Driving Schedule

1. Click  to display the Driving Schedule portion of the Vehicle Routing Wizard.
2. Make any changes to the schedule and click OK.
3. Click to run the vehicle routing procedure again with the changes to the vehicles.

To Modify the Route Duration, Route Balancing, and Other Settings

1. Click  to display the Options portion of the Vehicle Routing Wizard.
2. Make any changes to the options and click OK.
3. Click to run the vehicle routing procedure again with the changes to the options.

To Move a Stop to a Different Route

1. Click  in the Vehicle Routing Manager to activate the Move Stop tool.
2. Click on a stop, then click on the route to which you wish to add the stop. Where you click on the route will determine the sequence in which the stops are serviced. Stops earlier in the route will be unchanged; stops later in the route will be serviced after the inserted stop. You will be warned if moving a stop violates time window or vehicle capacity constraints.
3. If you click a location where there is more than one route, Maptitude displays the Pick Destination Route dialog box. Choose the route you wish to move the stop to and click OK.
4. The stop is removed from the sequence of stops in the initial route, and inserted into the new route. Maptitude recalculates the changed routes, highlights them on the map, and shows detailed information about the change in the Vehicle Routing Manager.
5. Click  to save the changes or click  to cancel the changes.

If you save the changes, Maptitude updates the changed routes and redraws the map.

To Add an Unserviced Stop to a Route

1. Click  in the Vehicle Routing Manager to activate the Add an Unserviced Stop tool.
2. Click on an unserviced stop, then click on the route at the location where you would like to move the stop. Where you click on the route will determine the sequence in which the stops are serviced. Stops earlier in the route will be unchanged; stops later in the route will be serviced after the inserted stop. You will be warned if moving a stop violates time window or vehicle capacity constraints.
3. If you click a location where there is more than one route, Maptitude displays the Pick Destination Route dialog box. Choose the route you wish to add the orphan to and click OK.
4. Maptitude recalculates the route with the new stop, highlights the new route on the map, and shows detailed information about the new route sequence in the Routing Deliveries & Pickups Manager. Any stops that violate time window constraints are shown in red in the scroll list.
5. Click  to save the changes or click  to cancel the changes.

If you save the changes, Maptitude inserts the unserviced stop into the route, and redraws the map with the new route.

To Remove a Stop from a Route

1. Click  in the Vehicle Routing Manager to activate the Drop Stop tool.
2. Click on the stop you wish to mark as unserviced.
3. Maptitude recalculates the route without the stop, highlights the new route on the map, and shows detailed information about the new route sequence in the Routing Deliveries & Pickups Manager. Any stops that violate time window constraints are shown in red in the scroll list.
4. Click  to save the changes or click  to cancel the changes.

If you save the changes, Maptitude removes the stop from the route and adds it to the unserviced stops selection set.

To Delete a Route

1. Click  in the Vehicle Routing Manager to activate the Delete Route tool.
2. Click on the route you wish to remove.
3. If you click a location where there is more than one route, Maptitude displays the Pick Destination Route dialog box. Choose the route you wish to delete and click OK.
4. Maptitude highlights the route on the map.
5. Click  to save the changes or click  to cancel the changes.

If you save the changes, Maptitude deletes the route, makes all of the stops along the route orphans, and adds them to the orphan selection set.

 

©2026 Caliper Corporation