[−][src]Module vrp_core::construction::constraints
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. |
| 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. |
| 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_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 stotal duration. |
| 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 context. |
| 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. |
Type Definitions
| AreaResolver | A function which returns operating area for given actor. |
| LocationResolver | A function which returns actual coordinate for given location. |
| TravelLimitFunc | A function which returns travel limits for given actor. |