Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Classes | Typedefs | Enumerations | Functions
operations_research::routing Namespace Reference

Common utilities for parsing routing instances. More...

Classes

class  Arc
 
class  CarpParser
 
struct  Coordinates2
 Real-world coordinates. More...
 
struct  Coordinates3
 
class  CVRPToursParser
 Class parsing tours (solution) data in CVRPlib format. More...
 
class  Edge
 
class  LiLimParser
 Li&Lim parser class. More...
 
class  NearpParser
 
class  PdTspParser
 
class  RoutingSolution
 
struct  SimpleTimeWindow
 
class  SolomonParser
 Solomon parser class. More...
 
class  SolomonSolutionParser
 Solomon solution parser class. More...
 
class  TspLibParser
 
class  TspLibTourParser
 Class parsing tour (solution) data in TSLIB95 format. More...
 
class  TspTWParser
 

Typedefs

typedef std::function< int64_t(int, int)> EdgeWeights
 Mapping between an edge (given by its tail and its head) and its weight.
 

Enumerations

enum class  RoutingOutputFormat {
  kNone , kTSPLIB , kCVRPLIB , kCARPLIB ,
  kNEARPLIB
}
 

Functions

::absl::Status ReadFile (absl::string_view file_name, CapacityPlanningInstance *request)
 
RoutingOutputFormat RoutingOutputFormatFromString (std::string_view format)
 
template<typename T>
std::string FormatStatistic (absl::string_view name, T value, RoutingOutputFormat format)
 Formats a solution or solver statistic according to the given format.
 
template<>
std::string FormatStatistic (absl::string_view name, double value, RoutingOutputFormat format)
 
template<typename T>
void PrintStatistic (absl::string_view name, T value, RoutingOutputFormat format)
 

Detailed Description

Common utilities for parsing routing instances.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A parser for CARPLIB instances. The base files are available online, as well as a description of the (Spanish-based) format: https://www.uv.es/belengue/carp.html ("CARPLIB") https://www.uv.es/~belengue/carp/READ_ME

The goal is to find routes starting and ending at a depot which visit a set of arcs (whereas a VRP visits nodes). The objective is to minimize the total cost, which is due to either servicing an edge (i.e. performing the required action) or traversing an edge (to get to another point in space). Not all arcs/edges in the graph must be serviced.

By this formulation, the total cost of servicing is known in advance. All vehicles start at the same node, the depot, having index 1. Servicing an edge requires resources, vehicles have a limited capacity. All vehicles have the same capacity.

The format of the data is the following:

NOMBRE : <INSTANCE-NAME> COMENTARIO : <ARBITRARY-COMMENT> VERTICES : <NUMBER-OF-NODES, int> ARISTAS_REQ : <NUMBER-OF-EDGES-WITH-NONZERO-SERVICING, int> ARISTAS_NOREQ : <NUMBER-OF-EDGES-WITH-ZERO-SERVICING, int> VEHICULOS : <NUMBER-OF-VEHICLES, int> CAPACIDAD : <CAPACITY-OF-EACH-VEHICLE, int> TIPO_COSTES_ARISTAS : EXPLICITOS COSTE_TOTAL_REQ : <TOTAL-SERVICING-COST> LISTA_ARISTAS_REQ : ( <HEAD-NODE-OF-EDGE, int>, <TAIL-NODE-OF-EDGE, int> ) coste <TRAVERSING-COST, int> demanda <SERVICING, int> <repeated, one edge per line> LISTA_ARISTAS_NOREQ : ( <HEAD-NODE-OF-EDGE, int>, <TAIL-NODE-OF-EDGE, int> ) coste <TRAVERSING-COST, int> <repeated, one edge per line> DEPOSITO : 1

While the file format is defined with 1-based indexing, the output of the parser is always 0-based. Users of this parser should never see any 1-based index; only 0-based index should be used to query values.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Reader for Multicommodity fixed-charge Network Design (MCND) files using the .dow format.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A parser for Li&Lim PDPTW (pickup and delivery problems with time windows) instances. The goal is to find routes starting and end at a depot which visit a set of nodes. Nodes are grouped in pairs of pickup and delivery nodes. The pickup node of each pair has to be performed before the delivery node and both nodes have to be on the same route. The objective is first to minimize the number of routes and then to minimize the total distance traveled, distances being measured with the Euclidean distance between nodes. Routes are subject to two other types of constraints:

  • time windows restricting the time during which a node can be visited,
  • vehicle capacity which limits the load of the vehicles performing the routes (each node has a corresponding demand which must be picked up or delivered by the vehicle).

The format of the data is the following:

  • one row to describe vehicles (which are all identical): <number of vehicles> <vehicle capacity> <speed>
  • followed by a row per node: <node id> <x> <y> <demand> <ready time> <due date> <service time> <pickup index> <delivery index>

Node 0 corresponds to the depot. For pickup nodes, pickup index is 0, and delivery index gives the index of the corresponding delivery node. For delivery tasks, delivery index is 0, and pickup index gives the index of the corresponding pickup node. The value of travel time is equal to the value of distance.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A parser for NEARPLIB instances. The base files are available online, as well as a description of the format: https://www.sintef.no/projectweb/top/nearp/documentation/

The goal is to find routes starting and ending at a depot which visit a set of arcs (directed), edges (undirected), and nodes, whereas a VRP only visits nodes. The objective is to minimize the total cost, which is due to either servicing a part of the graph (i.e. performing the required action) or traversing an edge (to get to another point in space). Not all arcs/edges in the graph must be serviced. These components are summarized in NEARP: node-edge-arc routing problem. The problem is sometimes also called MCGRP: mixed capacitated generalized routing problem.

All vehicles start at the same node, the depot. Its index is often 1, but many instances have another depot. Servicing a part of the graph requires resources, vehicles have a limited capacity. All vehicles have the same capacity.

The format of the data is the following (from https://www.sintef.no/projectweb/top/nearp/documentation/):

Name: <Instance name> Optimal value: <Optimal value, -1 if unknown> #Vehicles: <Max. number of vehicles, -1 if unconstrained> Capacity: <Vehicle capacity Q> Depot: <Index of depot node> #Nodes: <number of nodes> #Edges: <number of edges> #Arcs: <number of arcs> #Required N: <number of required nodes> #Required E: <number of required edges> #Required A: <number of required arcs>

% Required nodes: Ni q_i s_i NODE INDEX, DEMAND, SERVICE COST

% Required edges: Ek i j q_ij c_ij s_ij EDGE INDEX, FROM NODE, TO NODE, TRAVERSAL COST, DEMAND, SERVICE COST

% Non-required edges: NrEl i j c_ij EDGE INDEX, FROM NODE, TO NODE, TRAVERSAL COST

% Required arcs: Ar i j q_ij c_ij ARC INDEX, FROM NODE, TO NODE, TRAVERSAL COST, DEMAND, SERVICE COST

% Non-required arcs: NrAs i j c_ij ARC INDEX, FROM NODE, TO NODE, TRAVERSAL COST

For nodes, the index is of the form NX, where X is the node index (for instance, N1 is the first node that requires servicing). The elements of each section are not necessarily sorted. Nodes are indexed together, with no separation between those that require servicing and those that do not, from 1 to the number of nodes. Conversely, arcs and edges have separate indexing depending on whether they require indexing: E1 to EM all require servicing, NrE1 to NrEN do not, for a total of M + N edges (respectively, for arcs, A1 to AK and NrA1 to NrAL for K + L arcs).

While the file format is defined with 1-based indexing, the output of the parser is always 0-based. Users of this parser should never see any 1-based index; only 0-based index should be used to query values.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A TSPPD parser used to parse instances of Traveling Salesman Problems with pickup and delivery constraints. This format was created by Stefan Ropke. https://link.springer.com/article/10.1007%2Fs10107-008-0234-9

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A parser for "Solomon" instances. The Solomon file library is a set of Capacitated Vehicle Routing Problems with Time Windows created by Pr. Marius Solomon.

The goal is to find routes starting and ending at a depot which visit a set of nodes. The objective is first to minimize the number of routes and then to minimize the total distance traveled, distances being measured with the Euclidean distance. There are two types of constraints limiting the route lengths:

  • time windows restricting the time during which a node can be visited
  • vehicle capacity which limits the load of the vehicles performing the routes (each node has a corresponding demand which must be picked up by the vehicle).

The format of the data is the following:

<instance_name> VEHICLE NUMBER CAPACITY <number of nodes> <vehicle capacity> CUSTOMER CUST NO. XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME <node id> <x> <y> <demand> <ready time> <due date> <service time>

The parser supports both standard instance files and zipped archives containing multiple instances.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Utilities to serialize VRP-like solutions in standardised formats: either TSPLIB or CVRPLIB.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A TSPLIB parser. The TSPLIB is a library containing Traveling Salesman Problems and other vehicle routing problems. Limitations:

  • only TSP and CVRP files are currently supported.
  • XRAY1, XRAY2 and SPECIAL edge weight types are not supported.

Takes as input a data file, potentially gzipped. The data must follow the TSPLIB95 format (described at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/DOC.PS).

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A TSPTW parser.

Takes as input a data file, potentially gzipped. The data must follow the format described at http://lopez-ibanez.eu/tsptw-instances and https://homepages.dcc.ufmg.br/~rfsilva/tsptw.

Typedef Documentation

◆ EdgeWeights

typedef std::function<int64_t(int, int)> operations_research::routing::EdgeWeights

Mapping between an edge (given by its tail and its head) and its weight.

Definition at line 89 of file simple_graph.h.

Enumeration Type Documentation

◆ RoutingOutputFormat

enum class operations_research::routing::RoutingOutputFormat
strong

Indicates the format in which the output should be done. This enumeration is used for solutions and solver statistics.

Enumerator
kNone 
kTSPLIB 
kCVRPLIB 
kCARPLIB 
kNEARPLIB 

Definition at line 39 of file solution_serializer.h.

Function Documentation

◆ FormatStatistic() [1/2]

template<>
std::string operations_research::routing::FormatStatistic ( absl::string_view name,
double value,
RoutingOutputFormat format )
inline

Specialization for doubles to show a higher precision: without this specialization, 591.556557 is displayed as 591.557.

Definition at line 271 of file solution_serializer.h.

◆ FormatStatistic() [2/2]

template<typename T>
std::string operations_research::routing::FormatStatistic ( absl::string_view name,
T value,
RoutingOutputFormat format )

Formats a solution or solver statistic according to the given format.

Todo
(user): think about using an enum instead of names (or even a full-fledged struct/class) for the various types of fields.

For CARPLIB, the statistics do not have names, it's up to the user to memorize their order.

Definition at line 248 of file solution_serializer.h.

◆ PrintStatistic()

template<typename T>
void operations_research::routing::PrintStatistic ( absl::string_view name,
T value,
RoutingOutputFormat format )

Prints a formatted solution or solver statistic according to the given format.

Definition at line 290 of file solution_serializer.h.

◆ ReadFile()

absl::Status operations_research::routing::ReadFile ( absl::string_view file_name,
CapacityPlanningInstance * request )

implicit.

Definition at line 33 of file dow_parser.cc.

◆ RoutingOutputFormatFromString()

RoutingOutputFormat operations_research::routing::RoutingOutputFormatFromString ( std::string_view format)

Parses a user-provided description of the output format. Expected inputs look like (without quotes): "tsplib", "cvrplib", "carplib". Unrecognized strings are parsed as kNone.

Definition at line 30 of file solution_serializer.cc.