1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

//! 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.

/// A key which tracks latest arrival.
pub const LATEST_ARRIVAL_KEY: i32 = 1;
/// A key which tracks waiting time.
pub const WAITING_KEY: i32 = 2;
/// A key which tracks total distance.
pub const TOTAL_DISTANCE_KEY: i32 = 3;
/// A key which track total duration.
pub const TOTAL_DURATION_KEY: i32 = 4;
/// A key which track duration limit.
pub const LIMIT_DURATION_KEY: i32 = 5;

/// A key which tracks current vehicle capacity.
pub const CURRENT_CAPACITY_KEY: i32 = 11;
/// A key which tracks maximum vehicle capacity ahead in route.
pub const MAX_FUTURE_CAPACITY_KEY: i32 = 12;
/// A key which tracks maximum capacity backward in route.
pub const MAX_PAST_CAPACITY_KEY: i32 = 13;
/// A key which tracks reload intervals.
pub const RELOAD_INTERVALS_KEY: i32 = 14;
/// A key which tracks max load in tour.
pub const MAX_LOAD_KEY: i32 = 15;
/// A key which tracks total value.
pub const TOTAL_VALUE_KEY: i32 = 16;
/// A key which tracks tour order statistics.
pub const TOUR_ORDER_KEY: i32 = 17;

mod pipeline;
pub use self::pipeline::*;

mod area;
pub use self::area::*;

mod transport;
pub use self::transport::*;

mod capacity;
pub use self::capacity::*;

mod locking;
pub use self::locking::*;

mod tour_size;
pub use self::tour_size::*;

mod conditional;
pub use self::conditional::*;

mod fleet_usage;
pub use self::fleet_usage::*;

use crate::construction::heuristics::RouteContext;
use crate::models::problem::TransportCost;

/// Updates route schedule.
pub fn update_route_schedule(route_ctx: &mut RouteContext, transport: &(dyn TransportCost + Send + Sync)) {
    TransportConstraintModule::update_route_schedules(route_ctx, transport);
    TransportConstraintModule::update_route_states(route_ctx, transport);
    TransportConstraintModule::update_statistics(route_ctx, transport);
}