or-tools/examples/cpp/pdptw.cc File Reference

#include <vector>
#include "base/callback.h"
#include "base/commandlineflags.h"
#include "base/strtoint.h"
#include "base/file.h"
#include "base/split.h"
#include "base/mathutil.h"
#include "constraint_solver/routing.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Typedefs
typedef std::vector< std::pair < int, int > >	operations_research::Coordinates
	Vector of (x,y) node coordinates, *unscaled*, in some imaginary planar, metric grid.
Functions
	DEFINE_string (pdp_file,"","File containing the Pickup and Delivery Problem to solve.")
	Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.
	DEFINE_int32 (pdp_force_vehicles, 0,"Force the number of vehicles used (maximum number of routes.")
	DEFINE_bool (pdp_display_solution, false,"Displays the solution of the Pickup and Delivery Problem.")
int64	operations_research::Travel (const Coordinates *const coords, RoutingModel::NodeIndex from, RoutingModel::NodeIndex to)
	Returns the scaled Euclidean distance between two nodes, coords holding the coordinates of the nodes.
int64	operations_research::ServiceTime (const std::vector< int64 > *const service_times, RoutingModel::NodeIndex node)
	Returns the scaled service time at a given node, service_times holding the service times.
int64	operations_research::TravelPlusServiceTime (const Coordinates *const coords, const std::vector< int64 > *const service_times, RoutingModel::NodeIndex from, RoutingModel::NodeIndex to)
	Returns the scaled (distance plus service time) between two nodes, coords holding the coordinates of the nodes and service_times holding the service times.
int64	operations_research::Demand (const std::vector< int64 > *const demands, RoutingModel::NodeIndex from, RoutingModel::NodeIndex to)
	Returns the demand (quantity picked up or delivered) of a node, demands holds the demand of each node.
string	operations_research::VerboseOutput (const RoutingModel &routing, const Assignment &assignment, const Coordinates &coords, const std::vector< int64 > &service_times)
	Outputs a solution to the current model in a string.
bool	operations_research::SafeParseInt64Array (const string &str, std::vector< int64 > *parsed_int)
	An inefficient but convenient method to parse a whitespace-separated list of integers.
bool	operations_research::LoadAndSolve (const string &pdp_file)
	Builds and solves a model from a file in the format defined by Li & Lim (http://www.sintef.no/static/am/opti/projects/top/vrp/format_pdp.htm).
int	main (int argc, char **argv)
	namespace operations_research
Variables
const int64	operations_research::kScalingFactor = 1000
	Scaling factor used to scale up distances, allowing a bit more precision from Euclidean distances.

---

Function Documentation

DEFINE_bool	(	pdp_display_solution	,
		false	,
		"Displays the solution of the Pickup and Delivery Problem."
	)

DEFINE_int32	(	pdp_force_vehicles	,
		0
	)

DEFINE_string	(	pdp_file	,
		""	,
		"File containing the Pickup and Delivery Problem to solve."
	)

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.

Pickup and Delivery Problem with Time Windows. The overall objective is to minimize the length of the routes delivering quantities of goods between pickup and delivery locations, taking into account vehicle capacities and node time windows. Given a set of pairs of pickup and delivery nodes, find the set of routes visiting all the nodes, such that

• corresponding pickup and delivery nodes are visited on the same route,
• the pickup node is visited before the corresponding delivery node,
• the quantity picked up at the pickup node is the same as the quantity delivered at the delivery node,
• the total quantity carried by a vehicle at any time is less than its capacity,
• each node must be visited within its time window (time range during which the node is accessible). The maximum number of vehicles used (i.e. the number of routes used) is specified in the data but can be overriden using the --pdp_force_vehicles flag.

A further description of the problem can be found here: http://http://en.wikipedia.org/wiki/Vehicle_routing_problem http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.9965&rep=rep1&type=pdf. Reads data in the format defined by Li & Lim (http://www.sintef.no/static/am/opti/projects/top/vrp/format_pdp.htm).

int main	(	int	argc,
		char **	argv
	)

namespace operations_research

Definition at line 315 of file pdptw.cc.