Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cvrptw_lib.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// This header provides functions to help create random instances of the
15// vehicle routing problem; random capacities and random time windows.
16#ifndef OR_TOOLS_ROUTING_PARSERS_CVRPTW_LIB_H_
17#define OR_TOOLS_ROUTING_PARSERS_CVRPTW_LIB_H_
18
19#include <cstdint>
20#include <functional>
21#include <memory>
22#include <random>
23#include <string>
24#include <vector>
25
26#include "absl/types/span.h"
29
30namespace operations_research {
31
32typedef std::function<int64_t(RoutingNodeIndex, RoutingNodeIndex)>
34
35// Random seed generator.
36int32_t GetSeed(bool deterministic);
37
38// Location container, contains positions of orders and can be used to obtain
39// Manhattan distances/times between locations.
41 public:
42 LocationContainer(int64_t speed, bool use_deterministic_seed);
43 void AddLocation(int64_t x, int64_t y) {
44 locations_.push_back(Location(x, y));
45 }
46 void AddRandomLocation(int64_t x_max, int64_t y_max);
47 void AddRandomLocation(int64_t x_max, int64_t y_max, int duplicates);
54
57 int64_t SameLocationFromIndex(int64_t node1, int64_t node2) const;
58
59 private:
60 class Location {
61 public:
62 Location();
63 Location(int64_t x, int64_t y);
64 int64_t DistanceTo(const Location& location) const;
65 bool IsAtSameLocation(const Location& location) const;
66
67 private:
68 static int64_t Abs(int64_t value);
69
70 int64_t x_;
71 int64_t y_;
72 };
73
74 std::mt19937 randomizer_;
75 const int64_t speed_;
77};
78
79// Random demand.
81 public:
83 bool use_deterministic_seed);
84 void Initialize();
87
88 private:
89 std::unique_ptr<int64_t[]> demand_;
90 const int size_;
92 const bool use_deterministic_seed_;
93};
94
95// Service time (proportional to demand) + transition time callback.
97 public:
99 int64_t time_per_demand_unit,
104
105 private:
106 const int64_t time_per_demand_unit_;
109};
110
111// Stop service time + transition time callback.
113 public:
115 int64_t stop_time, const LocationContainer& location_container,
119
120 private:
121 const int64_t stop_time_;
122 const LocationContainer& location_container_;
125};
126
127// Route plan displayer.
128// TODO(user): Move the display code to the routing library.
131 const operations_research::RoutingModel& routing,
132 const operations_research::Assignment& plan, bool use_same_vehicle_costs,
133 int64_t max_nodes_per_group, int64_t same_vehicle_cost,
134 absl::Span<const std::string> dimension_names);
135
136} // namespace operations_research
137
138#endif // OR_TOOLS_ROUTING_PARSERS_CVRPTW_LIB_H_
int64_t ManhattanDistance(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Definition cvrptw_lib.cc:67
void AddRandomLocation(int64_t x_max, int64_t y_max)
Definition cvrptw_lib.cc:54
int64_t ManhattanTime(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Definition cvrptw_lib.cc:77
bool SameLocation(RoutingIndexManager::NodeIndex node1, RoutingIndexManager::NodeIndex node2) const
Definition cvrptw_lib.cc:81
void AddLocation(int64_t x, int64_t y)
Definition cvrptw_lib.h:43
LocationContainer(int64_t speed, bool use_deterministic_seed)
Definition cvrptw_lib.cc:49
int64_t NegManhattanDistance(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Definition cvrptw_lib.cc:72
int64_t SameLocationFromIndex(int64_t node1, int64_t node2) const
Definition cvrptw_lib.cc:87
int64_t Demand(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
RandomDemand(int size, RoutingIndexManager::NodeIndex depot, bool use_deterministic_seed)
ServiceTimePlusTransition(int64_t time_per_demand_unit, operations_research::RoutingNodeEvaluator2 demand, operations_research::RoutingNodeEvaluator2 transition_time)
int64_t Compute(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
StopServiceTimePlusTransition(int64_t stop_time, const LocationContainer &location_container, operations_research::RoutingNodeEvaluator2 transition_time)
int64_t Compute(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Common utilities for parsing routing instances.
In SWIG mode, we don't want anything besides these top-level includes.
void DisplayPlan(const RoutingIndexManager &manager, const RoutingModel &routing, const operations_research::Assignment &plan, bool use_same_vehicle_costs, int64_t max_nodes_per_group, int64_t same_vehicle_cost, absl::Span< const std::string > dimension_names)
int32_t GetSeed(bool deterministic)
Random seed generator.
Definition cvrptw_lib.cc:40
std::function< int64_t(RoutingNodeIndex, RoutingNodeIndex)> RoutingNodeEvaluator2
Definition cvrptw_lib.h:33
trees with all degrees equal to