operations_research::InsertionSequenceGenerator Class Reference

Generates insertion positions respecting structural constraints. More...

#include <routing_search.h>

Public Member Functions
	InsertionSequenceGenerator ()
void	AppendPickupDeliveryMultitourInsertions (int pickup, int delivery, int vehicle, const std::vector< int > &path, const std::vector< bool > &path_node_is_pickup, const std::vector< bool > &path_node_is_delivery, InsertionSequenceContainer &insertions)

Detailed Description

Generates insertion positions respecting structural constraints.

Definition at line 1011 of file routing_search.h.

Constructor & Destructor Documentation

InsertionSequenceGenerator()

operations_research::InsertionSequenceGenerator::InsertionSequenceGenerator ( )

inline

Definition at line 1013 of file routing_search.h.

Member Function Documentation

AppendPickupDeliveryMultitourInsertions()

void operations_research::InsertionSequenceGenerator::AppendPickupDeliveryMultitourInsertions	(	int	pickup,
		int	delivery,
		int	vehicle,
		const std::vector< int > &	path,
		const std::vector< bool > &	path_node_is_pickup,
		const std::vector< bool > &	path_node_is_delivery,
		InsertionSequenceContainer &	insertions )

Generates insertions for a pickup and delivery pair in a multitour path:

• a series of pickups may only start if all the deliveries of previous pickups have been performed.
• given a maximal pickup*delivery* subsequence, either the pickups or the deliveries are symmetric, meaning their order does not matter. Under these specifications, this method generates all unique insertions of the given pair that keep the multitour property.

  Note

  there are several ways one can extend pure pickup and delivery problems to mixed paired and unpaired visits. Two extreme views:

• multitour heuristics should consider that only consecutive pickups or consecutive deliveries have a symmetry. Heuristics should only break those symmetries, in the mixed case inserting a pair in a path of length p has O(p²) possibilities.
• multitour heuristics should not consider unpaired visits. Insertions are made on the subpath of paired nodes, all extensions to the original path that conserve order are equivalent.

Find insertion positions for the input pair, pickup P and delivery D.

Avoids duplicate insertions. If next_increase_[pos] - 1 == pos:

• append(pos, pos) is append(pos, next_increase_[pos] - 1)
• because is_after_decrease, with pos' = prev_decrease_[pos], next_increase_[pos'] == next_increase_[pos], so that append(prev_decrease_[pos], pos) is append(pos', next_increase_[pos'] - 1).

Downwards inflexion: vehicle is at its max. Avoids duplicate insertions, when next_decrease_[pos] - 1 == pos:

• append(pos, pos) is append(pos, next_decrease_[pos] - 1)
• because is_before_increase, with pos' = prev_increase_[pos], next_decrease_[pos'] == next_decrease_[pos], so that append(prev_increase_[pos], pos) is append(pos', next_decrease_[pos'] - 1).

Definition at line 2155 of file routing_search.cc.

---

The documentation for this class was generated from the following files:

• ortools/constraint_solver/routing_search.h
• ortools/constraint_solver/routing_search.cc