Module vrp_core::construction::constraints [−][src]
Various built-in constraints applied to customers and vehicles/drivers.
Constraint
Constraint represents some limitation which should be applied to solution. A good examples:
- time: customer can be visited only in specific time window, e.g. from 9am till 11am
- capacity: there is a fleet and multiple customers with total demand exceeding capacity of one vehicle from the fleet.
- shift-time: vehicle or driver cannot operate more than specific amount of time.
Typically, VRP can have many of such constraints applied to its solution.
Design
There are multiple types of constraints described below in details. In common, all of them try
to identify insertion possibility or cost of given customer known as Job
into given route.
Constraint characteristics
Each constraint has two characteristic:
-
hard or soft: this characteristic defines what should happen when constraint is violated. When hard constraint is violated, it means that given customer cannot be served with given route. In contrast to this, soft constraint allows insertion but applies some penalty to make violation less attractive.
-
route or activity: this characteristic defines on which level constrain is executed. As a heuristic algorithm is based on insertion heuristic, insertion of one customer is evaluated on each leg of one route. When it does not make sense, the route constraint can be used as it is called only once to check whether customer can be inserted in given route.
Constraint module
Sometimes you might need multiple constraints with different characteristics to implement some
aspect of VRP variation. This is where ConstraintModule
supposed to be used: it allows you
to group multiple constraints together keeping implementation details hidden outside of module.
Additionally, ConstraintModule
provides the way to share some state between insertions.
This is really important as allows you to avoid unneeded computations.
Sharing state
You can share some state using RouteState
object which is part of RouteContext
. It is
read-only during insertion evaluation in all constraint types, but it is mutable via ConstraintModule
methods once best insertion is identified.
Constraint pipeline
All constraint modules are organized inside one ConstraintPipeline
which specifies the order
of their execution.
Structs
ActivityConstraintViolation | Specifies result of hard route constraint check. |
Area | An area where actor is allowed to serve jobs. |
AreaModule | An area module provides way to restrict given actor to work in specific areas only. |
CapacityConstraintModule | A module which ensures vehicle capacity limitation while serving customer’s demand. |
ConcreteJobContextTransition | A concrete implementation of |
ConditionalJobModule | A module which allows to promote jobs between required and ignored collection using some condition. Useful to model some optional/conditional activities, e.g. breaks, refueling, etc. |
ConstraintPipeline | Provides the way to work with multiple constraints. |
FleetUsageConstraintModule | A module which controls fleet size usage. |
RouteConstraintViolation | Specifies result of hard route constraint check. |
StrictLockingModule | A module which allows to lock specific actors within specific jobs using different rules. |
TourSizeModule | Limits amount of job activities per tour. |
TransportConstraintModule | A module which checks whether vehicle can serve activity taking into account their time windows and traveling constraints. Also it is responsible for transport cost calculations. |
Enums
ConstraintVariant | A variant type for constraint types. |
Constants
CURRENT_CAPACITY_KEY | A key which tracks current vehicle capacity. |
LATEST_ARRIVAL_KEY | A key which tracks latest arrival. |
MAX_FUTURE_CAPACITY_KEY | A key which tracks maximum vehicle capacity ahead in route. |
MAX_LOAD_KEY | A key which tracks max load in tour. |
MAX_PAST_CAPACITY_KEY | A key which tracks maximum capacity backward in route. |
RELOAD_INTERVALS_KEY | A key which tracks reload intervals. |
TOTAL_DISTANCE_KEY | A key which tracks total distance. |
TOTAL_DURATION_KEY | A key which track total duration. |
TOTAL_VALUE_KEY | A key which tracks total value. |
WAITING_KEY | A key which tracks waiting time. |
Traits
ConstraintModule | Represents a constraint module which can be added to constraint pipeline. |
HardActivityConstraint | Specifies hard constraint which operates on activity level. |
HardRouteConstraint | Specifies hard constraint which operates on route level. |
JobContextTransition | Defines how jobs are moved in solution context. Index of original affected route context is passed. |
MultiTrip | This trait defines multi-trip strategy. |
SoftActivityConstraint | Specifies soft constraint which operates on activity level. |
SoftRouteConstraint | Specifies soft constraint which operates on route level. |
Functions
route_intervals | Returns intervals between vehicle terminal and reload activities. |
update_route_schedule | Updates route schedule. |
Type Definitions
AreaResolver | A function which returns operating areas for given actor. |
LocationResolver | A function which returns actual coordinate for given location. |
TourSizeResolver | A function which returns tour size limit for given actor. |
TravelLimitFunc | A function which returns travel limits for given actor. |