Please take a moment to read about the basics of this Routing App before starting to optimize.
Terminologies
-
Each location has a unique node number in the ordered set of locations where the customers
are arranged before the depots. Node numbers are indicated by the # symbol. Note that when
deleting locations, these numbers get updated to be in consecutive order.
-
The activity to be planned is called a request. A request may be a transporting order or
demand, such as a delivery from a depot to a customer, a pickup from a customer to a depot, or
a pickup and delivery between customers. Shipments may be loaded or unloaded and all operations on
vehicle loadings are element-wise.
For the case of a delivery the input demand value is negative and for a pickup the input
demand value is positive.
A request may also be a customer service order without any physical goods loaded. This case
is treated as a request with zero demand quantity.
-
The term customer refers to a location where a request occurs. A depot refers to a location
of no request.
Depot nodes may be warehouses, service stations, driver homes, parking places etc.
Depot nodes constitute start and end locations in a tour.
-
Each vehicle inherently represents a vehicle type by its associated
parameter values. Every used vehicle is associated a driver and a tour. A tour is a journey
starting at a vehicle’s start location and ending at its final location with at least one
interim location. The model assumes a unity of vehicle, driver, and tour. A tour may consist
of several trips (multiple trips).
Model configuration
-
The model configuration is the heart of this Routing App. It allows you to customize the
Routing Problem by choosing from a pool of various model attributes. You can read more about the model
attributes here.
-
The chosen model attributes determine which functions are part of the optimization.
Therefore, setting only input data is not sufficient to determine a routing model type.
In fact, all input data is read and passed to the optimization model but they are only applied
if the corresponding model attributes are set.
-
It is advisable to go through the categories in the order given. This is because there are
interdependencies between the attributes (e.g. single depot has no open routes attribute, or
no vehicle-depot incompatibilities for fixed start and end nodes). For a new project, you have
to proceed in the order given. If you have completed a configuration once, you may jump
between the categories.
-
Note that the attributes in category IV-Objectives are reset when the page is loaded.
-
In the objectives category, you may choose a single objective, weighted sum objective, or
hierarchical ordering. The latter is recommended for most basic vehicle routing problems.
For example, if you want to solve a classical routing problem with time windows, minimize
time violations with first priority and total distance with second priority.
(Tip: minimize nbVehicles as a first or second prioritized objective if this is appropriate.
This can accelerate the resolution process (better solution values in same running time) in
many cases).
-
The soft constraints can only be set with the hierarchical objectives attribute. They replace
corresponding hard constraints in case they have been selected before. Time violations and
route imbalance functions are only available as soft constraints (hence, the hierarchical
objectives attributes is necessary).
-
You find a list of selected configuration attributes used for the optimization run in the solutions
select menu (solution block).
Input data
- You can create and edit vehicles, customers, depots, and their relations. All input data is read and
passed to the optimization model but it is only applied if the corresponding model attributes are set.
Therefore, if you want specific input parameters to be used in the optimization, you must set the
corresponding attributes in the model configuration.
-
Because the model attributes determine which input data is applied, there is a general assumption made
regarding the particular database elements used for the optimization. For example, if there are two
depots in the database but you have selected the single depot model attribute, the optimization model
uses only the first depot in this case (the one with lower # value).
- Pickup request have negative demand values, delivery request have positive demand values,
and service requests have zero demand value. This applies in the optimization only if you have
selected the pickup and delivery model attribute. If you have selected the pickup or
delivery attribute, all demand values are changed to absolute values.
- The input units are indicated next to the forms. For the demand quantity, you may use your own unit
(expressible as integer value).
- Make sure that you have specified a start depot (end depot) in vehicle-depot-relations in case you
have selected the fixed start depots (fixed end depots) model attribute. If you have selected variable
depots or a single depot, this is not necessary.
- You can generate the distance and duration matrix in the input block. Make sure to update the matrix
when adding customer or depot addresses. With the free licence of the Google Distance Matrix API, the
matrix size currently has the following restrictions:
- nbDepots <25
- nbCustomers <25
- nbDepots * nbCustomers < 100
Optimization
- In the optimization block you can set the time limit, the simulated annealing level, the
number of threads, and the number of K-elements.
- The time limit is the running time in seconds of the optimization process. It is the
optimization stop criterion.
- The simulated annealing level can take values between 0 and 9 to control the solution
convergence process. If this parameter is set to zero, any deteriorating move is rejected. Higher
annealing level values increase the chance of “uphill” moves (deteriorating moves are allowed),
but the convergence of the search is potentially weakened. If the search space is highly
constrained, you may consider using a high annealing level.
-
The number of threads determines the degree of computational parallelization. The search strategy
of LocalSolver is multi-threaded by default. If you encounter any unexpected problems, you may
consider disabling the multi thread approach (setting nbThreads = 1). LocalSolver reports more
about
possible issues
here.
- The number of K-elements is the number of sequence subsets passed to the optimization model.
This is equal to the maximum number of vehicles/tours available for the optimization run. The
multi-start acceleration strategy for determining the optimal number of K-elements for the
resolution process (mentioned in master thesis) has been implemented in a batch script and is
currently not available for the Linux system (disabled for university server).
- You may call the optimize function when:
- at least one vehicle in database
- at least two customers in database
- at least one depot in database
- distance matrix is generated (and up-to-date)
- model configuration is complete (step 4)
Solution
- When the optimization process has terminated, the solution block displays updated information about
the time of the last run and the status of the solution. The status can be "feasible", "infeasible",
or "error". A solution is feasible if all constraints hold and it is infeasible if any constraint is
violated.
An error occurs in case of data input inconsistency (e.g. vehicle-customer must-serve and
vehicle-customer incompatibility).
- You can display the sequence solutions for each used vehicle in the optimization (if the solution is
feasible). Using a free licence in the Google Waypoint API, the number of visits in each tour is
restricted to 23 customers +2 depots for routes display.
-
You can access different solution output files in the select menu. Check the solution readme for more
information.
Error control
- if an error occurs during the optimization, see if you can identify any of the following common
error sources
- You have selected fixed start and/or fixed end depot attribute but you did not specify the
depots
in the input (in vehicle-depot relation)
- You have specified two fixed start or end nodes for a single vehicle; or variable start nodes
but all incompatible
- You already have selected objective attributes and jump back to another category to change
settings. Be aware that attribute changes may effect attributes in later categories. It is advised
to go through the categories in the order given.
- When minimizing time violations, check for time inconsistencies (customer time windows before
vehicle start times, closing time is zero (default value), lunch duration larger than the
difference between earliest and latest possible lunch, etc.)
- You have selected the multiple depots attribute but you have a single depot in the database
- Distance Matrix not refreshed after new depot or customer creation
- You minimize cost but cost factors are zero (default value)
-
Pay attention to the ordering of objectives when selecting a hierarchy.
A bad example: 1. Minimize time violations, 2. Maximize number of visits, 3. Minimize total
distance.
A good example: 1. Maximize number of visits, 2. Minimize time violations, 3. Minimize total
distance.
-
Note that the current version only supports a single planning day and time is measured in minutes from
midnight. Time windows spanning in the next day are currently not supported (no error but nonsensical
results).
- This Routing App is a prototype and not all errors are controlled.
If you encounter an error, which is not mentioned here, you may want to go through the model
configuration again. It can be possible that opening and closing different collapsible elements on the
same page causes an error when translating the chosen attributes into variables for the optimization
model. It is generally advised to go through the configuration in the given order.
Notes:
You must have an internet connection in order to use the web-application (for matrix creation). You must
have Javascript supported by your operating browser to use the app.
Logo inspired by the
Traveller's Dodecahedron
