vrp_pragmatic/format/problem/
model.rs

1#[cfg(test)]
2#[path = "../../../tests/unit/format/problem/model_test.rs"]
3mod model_test;
4
5extern crate serde_json;
6
7use crate::format::{FormatError, Location, MultiFormatError};
8use serde::{Deserialize, Serialize};
9use std::io::{BufReader, BufWriter, Error, Read, Write};
10use vrp_core::prelude::Float;
11// region Plan
12
13/// Relation type.
14#[derive(Clone, Deserialize, Debug, Serialize)]
15#[serde(rename_all = "camelCase")]
16pub enum RelationType {
17    /// Relation type which locks jobs to specific vehicle in any order.
18    Any,
19    /// Relation type which locks jobs in specific order allowing insertion of other jobs in between.
20    Sequence,
21    /// Relation type which locks jobs in strict order, no insertions in between are allowed.
22    Strict,
23}
24
25/// Relation is the way to lock specific jobs to specific vehicles.
26#[derive(Clone, Deserialize, Debug, Serialize)]
27#[serde(rename_all = "camelCase")]
28pub struct Relation {
29    /// Relation type.
30    #[serde(rename(deserialize = "type", serialize = "type"))]
31    pub type_field: RelationType,
32    /// List of job ids.
33    pub jobs: Vec<String>,
34    /// Vehicle id.
35    pub vehicle_id: String,
36    /// Vehicle shift index.
37    #[serde(skip_serializing_if = "Option::is_none")]
38    pub shift_index: Option<usize>,
39}
40
41/// A job skills limitation for a vehicle.
42#[derive(Clone, Deserialize, Debug, Serialize)]
43#[serde(rename_all = "camelCase")]
44pub struct JobSkills {
45    /// Vehicle should have all of these skills defined.
46    #[serde(skip_serializing_if = "Option::is_none")]
47    pub all_of: Option<Vec<String>>,
48    /// Vehicle should have at least one of these skills defined.
49    #[serde(skip_serializing_if = "Option::is_none")]
50    pub one_of: Option<Vec<String>>,
51    /// Vehicle should have none of these skills defined.
52    #[serde(skip_serializing_if = "Option::is_none")]
53    pub none_of: Option<Vec<String>>,
54}
55
56/// Specifies a place for sub job.
57#[derive(Clone, Deserialize, Debug, Serialize)]
58pub struct JobPlace {
59    /// A job place location.
60    pub location: Location,
61    /// A job place duration (service time).
62    pub duration: Float,
63    /// A list of job place time windows with time specified in RFC3339 format.
64    #[serde(skip_serializing_if = "Option::is_none")]
65    pub times: Option<Vec<Vec<String>>>,
66    /// A tag which will be propagated back within corresponding activity in solution.
67    /// You can use it to identify used place in solution.
68    #[serde(skip_serializing_if = "Option::is_none")]
69    pub tag: Option<String>,
70}
71
72/// Specifies a job task.
73#[derive(Clone, Deserialize, Debug, Serialize)]
74pub struct JobTask {
75    /// A list of possible places where given task can be performed.
76    pub places: Vec<JobPlace>,
77    /// Job place demand.
78    #[serde(skip_serializing_if = "Option::is_none")]
79    pub demand: Option<Vec<i32>>,
80    /// An order, bigger value - later assignment in the route.
81    #[serde(skip_serializing_if = "Option::is_none")]
82    pub order: Option<i32>,
83}
84
85/// A customer job model. Actual tasks of the job specified by list of pickups and deliveries
86/// which follows these rules:
87/// * all of them should be completed or none of them.
88/// * all pickups must be completed before any of deliveries.
89#[derive(Clone, Deserialize, Debug, Serialize)]
90pub struct Job {
91    /// A job id.
92    pub id: String,
93
94    /// A list of pickup tasks.
95    #[serde(skip_serializing_if = "Option::is_none")]
96    pub pickups: Option<Vec<JobTask>>,
97
98    /// A list of delivery tasks.
99    #[serde(skip_serializing_if = "Option::is_none")]
100    pub deliveries: Option<Vec<JobTask>>,
101
102    /// A list of replacement tasks.
103    #[serde(skip_serializing_if = "Option::is_none")]
104    pub replacements: Option<Vec<JobTask>>,
105
106    /// A list of service tasks.
107    #[serde(skip_serializing_if = "Option::is_none")]
108    pub services: Option<Vec<JobTask>>,
109
110    /// A job skills limitations for serving a job.
111    #[serde(skip_serializing_if = "Option::is_none")]
112    pub skills: Option<JobSkills>,
113
114    /// Job value, bigger value - more chances for assignment.
115    #[serde(skip_serializing_if = "Option::is_none")]
116    pub value: Option<Float>,
117
118    /// Job group: jobs of the same group are assigned to the same tour or unassigned.
119    #[serde(skip_serializing_if = "Option::is_none")]
120    pub group: Option<String>,
121
122    /// A compatibility group: jobs with different compatibility cannot be assigned to the same tour.
123    #[serde(skip_serializing_if = "Option::is_none")]
124    pub compatibility: Option<String>,
125}
126
127// region Clustering
128
129/// Specifies clustering algorithm.
130#[derive(Clone, Deserialize, Debug, Serialize)]
131#[serde(tag = "type")]
132pub enum Clustering {
133    /// Vicinity clustering.
134    #[serde(rename(deserialize = "vicinity", serialize = "vicinity"))]
135    Vicinity {
136        /// Specifies a vehicle profile used to calculate commute duration and distance between
137        /// activities in the single stop.
138        profile: VehicleProfile,
139        /// Specifies threshold information.
140        threshold: VicinityThresholdPolicy,
141        /// Specifies visiting policy.
142        visiting: VicinityVisitPolicy,
143        /// Specifies service time policy.
144        serving: VicinityServingPolicy,
145        /// Specifies filtering policy.
146        filtering: Option<VicinityFilteringPolicy>,
147    },
148}
149
150/// Defines a various thresholds to control cluster size.
151#[derive(Clone, Deserialize, Debug, Serialize)]
152#[serde(rename_all = "camelCase")]
153pub struct VicinityThresholdPolicy {
154    /// Moving duration limit.
155    pub duration: Float,
156    /// Moving distance limit.
157    pub distance: Float,
158    /// Minimum shared time for jobs (non-inclusive).
159    pub min_shared_time: Option<Float>,
160    /// The smallest time window of the cluster after service time shrinking.
161    pub smallest_time_window: Option<Float>,
162    /// The maximum amount of jobs per cluster.
163    pub max_jobs_per_cluster: Option<usize>,
164}
165
166/// Specifies cluster visiting policy.
167#[derive(Clone, Deserialize, Debug, Serialize)]
168#[serde(rename_all = "camelCase")]
169pub enum VicinityVisitPolicy {
170    /// It is required to return to the first job's location (cluster center) before visiting a next job.
171    Return,
172    /// Clustered jobs are visited one by one from the cluster center finishing in the end at the
173    /// first job's location.
174    Continue,
175}
176
177/// Specifies service time policy.
178#[derive(Clone, Deserialize, Debug, Serialize)]
179#[serde(tag = "type")]
180pub enum VicinityServingPolicy {
181    /// Keep original service time.
182    #[serde(rename(deserialize = "original", serialize = "original"))]
183    Original {
184        /// Parking time.
185        parking: Float,
186    },
187    /// Correct service time by some multiplier.
188    #[serde(rename(deserialize = "multiplier", serialize = "multiplier"))]
189    Multiplier {
190        /// Multiplier value applied to original job's duration.
191        value: Float,
192        /// Parking time.
193        parking: Float,
194    },
195    /// Use fixed value for all clustered jobs.
196    #[serde(rename(deserialize = "fixed", serialize = "fixed"))]
197    Fixed {
198        /// Fixed value used for all jobs in the cluster.
199        value: Float,
200        /// Parking time.
201        parking: Float,
202    },
203}
204
205/// Specifies filtering policy for vicinity clustering.
206#[derive(Clone, Deserialize, Debug, Serialize)]
207#[serde(rename_all = "camelCase")]
208pub struct VicinityFilteringPolicy {
209    /// Ids of the jobs which cannot be used within clustering.
210    pub exclude_job_ids: Vec<String>,
211}
212
213// endregion
214
215/// A plan specifies work which has to be done.
216#[derive(Clone, Deserialize, Debug, Serialize)]
217pub struct Plan {
218    /// List of jobs.
219    pub jobs: Vec<Job>,
220
221    /// List of relations between jobs and vehicles.
222    #[serde(skip_serializing_if = "Option::is_none")]
223    pub relations: Option<Vec<Relation>>,
224
225    /// Specifies clustering parameters.
226    #[serde(skip_serializing_if = "Option::is_none")]
227    pub clustering: Option<Clustering>,
228}
229
230// endregion
231
232// region Fleet
233
234/// Specifies vehicle costs.
235#[derive(Clone, Deserialize, Debug, Serialize)]
236pub struct VehicleCosts {
237    /// Fixed is cost of vehicle usage per tour.
238    #[serde(skip_serializing_if = "Option::is_none")]
239    pub fixed: Option<Float>,
240
241    /// Cost per distance unit.
242    pub distance: Float,
243
244    /// Cost per time unit.
245    pub time: Float,
246}
247
248/// Specifies vehicle shift start.
249#[derive(Clone, Deserialize, Debug, Serialize)]
250pub struct ShiftStart {
251    /// Earliest possible departure date time in RFC3339 format.
252    pub earliest: String,
253
254    /// Latest possible departure date time in RFC3339 format. If omitted, departure time
255    /// theoretically can be shifted till arrival. Set this value, if you want to limit
256    /// departure time optimization.
257    #[serde(skip_serializing_if = "Option::is_none")]
258    pub latest: Option<String>,
259
260    /// Shift start location.
261    pub location: Location,
262}
263
264/// Specifies vehicle shift end.
265#[derive(Clone, Deserialize, Debug, Serialize)]
266pub struct ShiftEnd {
267    /// Earliest possible arrival date time in RFC3339 format.
268    /// At the moment, not supported, reserved for future.
269    #[serde(skip_serializing_if = "Option::is_none")]
270    pub earliest: Option<String>,
271
272    /// Latest possible arrival date time in RFC3339 format.
273    pub latest: String,
274
275    /// Shift end location.
276    pub location: Location,
277}
278
279/// Specifies vehicle shift.
280#[derive(Clone, Deserialize, Debug, Serialize)]
281pub struct VehicleShift {
282    /// Vehicle shift start.
283    pub start: ShiftStart,
284
285    /// Vehicle shift end.
286    #[serde(skip_serializing_if = "Option::is_none")]
287    pub end: Option<ShiftEnd>,
288
289    /// Vehicle breaks.
290    #[serde(skip_serializing_if = "Option::is_none")]
291    pub breaks: Option<Vec<VehicleBreak>>,
292
293    /// Vehicle reloads which allows vehicle to visit place where goods can be loaded or
294    /// unloaded during single tour.
295    #[serde(skip_serializing_if = "Option::is_none")]
296    pub reloads: Option<Vec<VehicleReload>>,
297
298    /// Vehicle recharge stations information.
299    #[serde(skip_serializing_if = "Option::is_none")]
300    pub recharges: Option<VehicleRecharges>,
301}
302
303/// Specifies a place where vehicle can load or unload cargo.
304#[derive(Clone, Deserialize, Debug, Serialize)]
305#[serde(rename_all = "camelCase")]
306pub struct VehicleReload {
307    /// A place location.
308    pub location: Location,
309
310    /// A total loading/reloading duration (service time).
311    pub duration: Float,
312
313    /// A list of time windows with time specified in RFC3339 format.
314    #[serde(skip_serializing_if = "Option::is_none")]
315    pub times: Option<Vec<Vec<String>>>,
316
317    /// A tag which will be propagated back within corresponding activity in solution.
318    #[serde(skip_serializing_if = "Option::is_none")]
319    pub tag: Option<String>,
320
321    /// A shared reload resource id.
322    #[serde(skip_serializing_if = "Option::is_none")]
323    pub resource_id: Option<String>,
324}
325
326/// Specifies vehicle recharge stations data.
327#[derive(Clone, Deserialize, Debug, Serialize)]
328#[serde(rename_all = "camelCase")]
329pub struct VehicleRecharges {
330    /// Maximum traveled distance before recharge station has to be visited.
331    pub max_distance: Float,
332
333    /// Specifies list of recharge station. Each can be visited only once.
334    pub stations: Vec<VehicleRechargeStation>,
335}
336
337/// Specifies type alias for vehicle recharge station.
338pub type VehicleRechargeStation = JobPlace;
339
340/// Vehicle limits.
341#[derive(Clone, Deserialize, Debug, Serialize)]
342#[serde(rename_all = "camelCase")]
343pub struct VehicleLimits {
344    /// Max traveling distance per shift/tour.
345    /// No distance restrictions when omitted.
346    #[serde(skip_serializing_if = "Option::is_none")]
347    pub max_distance: Option<Float>,
348
349    /// Max duration per tour.
350    /// No time restrictions when omitted.
351    #[serde(skip_serializing_if = "Option::is_none")]
352    #[serde(alias = "shiftTime")]
353    pub max_duration: Option<Float>,
354
355    /// Max amount job activities.
356    /// No job activities restrictions when omitted.
357    #[serde(skip_serializing_if = "Option::is_none")]
358    pub tour_size: Option<usize>,
359}
360
361/// Vehicle optional break time variant.
362#[derive(Clone, Deserialize, Debug, Serialize)]
363#[serde(untagged)]
364pub enum VehicleOptionalBreakTime {
365    /// Break time is defined by a time window with time specified in RFC3339 format.
366    TimeWindow(Vec<String>),
367    /// Break time is defined by a time offset range.
368    TimeOffset(Vec<Float>),
369}
370
371/// Vehicle required break time variant.
372#[derive(Clone, Deserialize, Debug, Serialize)]
373#[serde(untagged)]
374pub enum VehicleRequiredBreakTime {
375    /// Break time is defined by exact time in RFC3339 format.
376    /// Break should be taken not earlier and not later than time range specified.
377    ExactTime {
378        /// Start of the range.
379        earliest: String,
380        /// End of the range.
381        latest: String,
382    },
383    /// Break time is defined by amount of seconds since driving time.
384    /// Break should be taken not earlier and not later than time range specified.
385    OffsetTime {
386        /// Start of the range.
387        earliest: Float,
388        /// End of the range.
389        latest: Float,
390    },
391}
392
393/// Vehicle break place.
394#[derive(Clone, Deserialize, Debug, Serialize)]
395pub struct VehicleOptionalBreakPlace {
396    /// Break duration.
397    pub duration: Float,
398    /// Break location.
399    #[serde(skip_serializing_if = "Option::is_none")]
400    pub location: Option<Location>,
401    /// A tag which will be propagated back within corresponding activity in solution.
402    #[serde(skip_serializing_if = "Option::is_none")]
403    pub tag: Option<String>,
404}
405
406/// Vehicle break policy.
407#[derive(Clone, Deserialize, Debug, Serialize)]
408#[serde(rename_all = "kebab-case")]
409pub enum VehicleOptionalBreakPolicy {
410    /// Allows to skip break if actual tour schedule doesn't intersect with vehicle time window.
411    SkipIfNoIntersection,
412    /// Allows to skip break if vehicle arrives before break's time window end.
413    SkipIfArrivalBeforeEnd,
414}
415
416/// Specifies a vehicle break.
417#[derive(Clone, Deserialize, Debug, Serialize)]
418#[serde(untagged)]
419pub enum VehicleBreak {
420    /// An optional break which is more flexible, but might be not assigned.
421    Optional {
422        /// Break time.
423        time: VehicleOptionalBreakTime,
424        /// Vehicle break places.
425        places: Vec<VehicleOptionalBreakPlace>,
426        /// Specifies vehicle break policy.
427        policy: Option<VehicleOptionalBreakPolicy>,
428    },
429    /// A break which has to be assigned. It is less flexible than optional break, but has strong
430    /// assignment guarantee.
431    Required {
432        /// Break time.
433        time: VehicleRequiredBreakTime,
434        /// Break duration.
435        duration: Float,
436    },
437}
438
439/// Specifies a vehicle type.
440#[derive(Clone, Deserialize, Debug, Serialize)]
441#[serde(rename_all = "camelCase")]
442pub struct VehicleType {
443    /// Vehicle type id.
444    pub type_id: String,
445
446    /// Concrete vehicle ids.
447    pub vehicle_ids: Vec<String>,
448
449    /// Vehicle profile.
450    pub profile: VehicleProfile,
451
452    /// Vehicle costs.
453    pub costs: VehicleCosts,
454
455    /// Vehicle shifts.
456    pub shifts: Vec<VehicleShift>,
457
458    /// Vehicle capacity.
459    pub capacity: Vec<i32>,
460
461    /// Vehicle skills.
462    #[serde(skip_serializing_if = "Option::is_none")]
463    pub skills: Option<Vec<String>>,
464
465    /// Vehicle limits.
466    #[serde(skip_serializing_if = "Option::is_none")]
467    pub limits: Option<VehicleLimits>,
468}
469
470/// Specifies a vehicle profile.
471#[derive(Clone, Deserialize, Debug, Serialize)]
472pub struct VehicleProfile {
473    /// Routing matrix profile name.
474    pub matrix: String,
475
476    /// Traveling duration scale factor.
477    /// Default value is 1.
478    #[serde(skip_serializing_if = "Option::is_none")]
479    pub scale: Option<Float>,
480}
481
482/// Specifies routing matrix profile.
483#[derive(Clone, Deserialize, Debug, Serialize)]
484pub struct MatrixProfile {
485    /// Profile name.
486    pub name: String,
487
488    /// Approximation speed (meters per second). Used only when routing matrix is not specified.
489    /// Default value is 10.
490    #[serde(skip_serializing_if = "Option::is_none")]
491    pub speed: Option<Float>,
492}
493
494/// Specifies vehicle resource type.
495#[derive(Clone, Deserialize, Debug, Serialize)]
496#[serde(tag = "type")]
497pub enum VehicleResource {
498    /// A shared reload resource.
499    #[serde(rename(deserialize = "reload", serialize = "reload"))]
500    Reload {
501        /// Resource id.
502        id: String,
503        /// A total resource capacity.
504        capacity: Vec<i32>,
505    },
506}
507
508/// Specifies fleet.
509#[derive(Clone, Deserialize, Debug, Serialize)]
510pub struct Fleet {
511    /// Vehicle types.
512    pub vehicles: Vec<VehicleType>,
513
514    /// Routing profiles.
515    pub profiles: Vec<MatrixProfile>,
516
517    /// Specifies vehicle resources.
518    #[serde(skip_serializing_if = "Option::is_none")]
519    pub resources: Option<Vec<VehicleResource>>,
520}
521
522// endregion
523
524// region Objective
525
526/// Specifies objective function types.
527#[derive(Clone, Deserialize, Debug, Serialize)]
528#[serde(tag = "type", rename_all = "kebab-case")]
529pub enum Objective {
530    /// An objective to minimize total cost as a linear combination of total time and distance.
531    MinimizeCost,
532
533    /// An objective to minimize total distance.
534    MinimizeDistance,
535
536    /// An objective to minimize total duration.
537    MinimizeDuration,
538
539    /// An objective to minimize total tour amount.
540    MinimizeTours,
541
542    /// An objective to maximize total tour amount.
543    MaximizeTours,
544
545    /// An objective to maximize value of served jobs.
546    MaximizeValue {
547        /// Specifies a weight of skipped breaks.
548        #[serde(skip_serializing_if = "Option::is_none")]
549        breaks: Option<Float>,
550    },
551
552    /// An objective to minimize number of unassigned jobs.
553    MinimizeUnassigned {
554        /// A skipped break weight to increase/decrease break is importance.
555        /// Default is 1.
556        #[serde(skip_serializing_if = "Option::is_none")]
557        breaks: Option<Float>,
558    },
559
560    /// An objective to minimize sum of arrival times from all routes.
561    MinimizeArrivalTime,
562
563    /// An objective to balance max load across all tours.
564    BalanceMaxLoad,
565
566    /// An objective to balance activities across all tours.
567    BalanceActivities,
568
569    /// An objective to balance distance across all tours.
570    BalanceDistance,
571
572    /// An objective to balance duration across all tours.
573    BalanceDuration,
574
575    /// An objective to control how tours are built.
576    CompactTour {
577        /// Specifies radius of neighbourhood. Min is 1.
578        job_radius: usize,
579    },
580
581    /// An objective to control order of job activities in the tour.
582    TourOrder,
583
584    /// An objective to prefer jobs to be served as soon as possible.
585    FastService,
586
587    /// A multi objective allows to define multiple competitive objectives at the same layer of hierarchy.
588    MultiObjective {
589        /// An objective composition type.
590        strategy: MultiStrategy,
591        /// Competitive objectives except `Composite` type (nesting is currently not supported).
592        objectives: Vec<Objective>,
593    },
594}
595
596/// An mupltiple objective strategy type specifies how competitive objective functions are compared
597/// among each other.
598#[derive(Clone, Deserialize, Debug, Serialize)]
599#[serde(tag = "name", rename_all = "kebab-case")]
600pub enum MultiStrategy {
601    /// A sum type simply sums all objective values together.
602    Sum,
603
604    /// A weighted sum type uses linear combination of weights and the corresponding fitness values.
605    WeightedSum {
606        /// Individual weights. Size of vector must be the same as amount of objective functions.
607        weights: Vec<Float>,
608    },
609}
610
611// endregion
612
613// region Common
614
615/// A VRP problem definition.
616#[derive(Clone, Deserialize, Debug, Serialize)]
617pub struct Problem {
618    /// Problem plan: customers to serve.
619    pub plan: Plan,
620
621    /// Problem resources: vehicles to be used, routing info.
622    pub fleet: Fleet,
623
624    /// Specifies objective functions in lexicographical order.
625    #[serde(skip_serializing_if = "Option::is_none")]
626    pub objectives: Option<Vec<Objective>>,
627}
628
629/// A routing matrix.
630#[derive(Clone, Deserialize, Debug, Serialize)]
631#[serde(rename_all = "camelCase")]
632pub struct Matrix {
633    /// A name of profile.
634    pub profile: Option<String>,
635
636    /// A date in RFC3999 for which routing info is applicable.
637    pub timestamp: Option<String>,
638
639    /// Travel distances (used to be in seconds).
640    #[serde(alias = "durations")]
641    pub travel_times: Vec<i64>,
642
643    /// Travel durations (use to be in meters).
644    pub distances: Vec<i64>,
645
646    /// Error codes to mark unreachable locations.
647    #[serde(skip_serializing_if = "Option::is_none")]
648    pub error_codes: Option<Vec<i64>>,
649}
650
651// endregion
652
653impl Job {
654    /// Returns iterator over all tasks.
655    pub fn all_tasks_iter(&self) -> impl Iterator<Item = &JobTask> {
656        self.pickups
657            .iter()
658            .chain(self.deliveries.iter())
659            .chain(self.services.iter())
660            .chain(self.replacements.iter())
661            .flatten()
662    }
663}
664
665/// Deserializes problem in json format from `BufReader`.
666pub fn deserialize_problem<R: Read>(reader: BufReader<R>) -> Result<Problem, MultiFormatError> {
667    serde_json::from_reader(reader).map_err(|err| {
668        vec![FormatError::new(
669            "E0000".to_string(),
670            "cannot deserialize problem".to_string(),
671            format!("check input json: '{err}'"),
672        )]
673        .into()
674    })
675}
676
677/// Deserializes routing matrix in json format from `BufReader`.
678pub fn deserialize_matrix<R: Read>(reader: BufReader<R>) -> Result<Matrix, MultiFormatError> {
679    serde_json::from_reader(reader).map_err(|err| {
680        vec![FormatError::new(
681            "E0001".to_string(),
682            "cannot deserialize matrix".to_string(),
683            format!("check input json: '{err}'"),
684        )]
685        .into()
686    })
687}
688
689/// Deserializes json list of locations from `BufReader`.
690pub fn deserialize_locations<R: Read>(reader: BufReader<R>) -> Result<Vec<Location>, MultiFormatError> {
691    serde_json::from_reader(reader).map_err(|err| {
692        vec![FormatError::new(
693            "E0000".to_string(),
694            "cannot deserialize locations".to_string(),
695            format!("check input json: '{err}'"),
696        )]
697        .into()
698    })
699}
700
701/// Serializes `problem` in json from `writer`.
702pub fn serialize_problem<W: Write>(problem: &Problem, writer: &mut BufWriter<W>) -> Result<(), Error> {
703    serde_json::to_writer_pretty(writer, problem).map_err(Error::from)
704}
vrp_pragmatic/format/problem/model.rs

vrp_pragmatic/format/problem/
model.rs
