CVRP-TW: eoVRPInit Class Reference

void eoVRPInit::operator() ( eoVRP & _gen ) [inline]

Functor member.

Initializes a genotype using an heuristic initializer.

Parameters:

_gen

Generally a genotype that has been default-constructed. Whatever it contains will be lost.

Definition at line 99 of file eoVRPInit.h.

References HeuristicInitialization().

void eoVRPInit::HeuristicInitialization ( eoVRP & _gen ) [inline, private]

Heuristic initializer.

This initializer constructs and individual from routes. Each route is built in a constructive way. The first client of each route is selected trying to maximize a function depending on its time window and how far it is from the depot. We always try to select the hardest clients as seeds. Used seeds are stored so that different seeds are selected for different individuals and thus guarantee the diversity of the initial population.

Parameters:

_gen

The individual to be initialized.

Definition at line 123 of file eoVRPInit.h.

References eoVRPUtils::clients, createNewRoute(), and EO< F >::invalidate().

Referenced by operator()().

bool eoVRPInit::createNewRoute	(	std::vector< int > &	_unvisited,
		int &	_unvisitedIdx,
		bool	_seedCheckingOverride,
		Route &	_route
	)			`[inline, private]`

Creates a new route.

Creates a new route selecting the best (hardest) client as seed and then adding the cheapest clients until one of the constraints (time window or vehicle's capacity) is broken.

Parameters:

	_unvisited	Vector of unvisited and thus available clients for constructing the new route.
	_unvisitedIdx	Position of the last univisted client in _unvisited vector.
	_seedCheckingOverride	If true, it overrides the seed checking mecanism. It must be always false for the first route and then true for the following ones. This way we will preserve diversity in our initial population as every individual will be initialized from a different initial route.
	_route	The brand new route we have constructed.

Returns:: True if everything went ok.

Definition at line 176 of file eoVRPInit.h.

References mSeedsUsed, mSeedsUsedCount, selectBestClientAsSeed(), and selectBestInsertion().

Referenced by HeuristicInitialization().

bool eoVRPInit::selectBestInsertion	(	std::vector< int > &	_unvisited,
		unsigned	_unvisitedIdx,
		Route &	_route,
		unsigned &	_nextClient,
		Route::iterator &	_it
	)			`[inline, private]`

Selects the best client and the best position for its insertion in a given route.

Given a subroute, this method tries to find the best client and the best position for it among all the univisited clients.

Parameters:

	_unvisited	Vector of unvisited and thus available clients for constructing the new route.
	_unvisitedIdx	Position of the last univisted client in _unvisited vector.
	_route	The route where we are trying to insert a new client.
	_nextClient	A return value. The selected client to be inserted.
	_it	A return value. The position for selected client to be inserted.

Returns:: True if a new insertion is possible. False otherwise.

Definition at line 249 of file eoVRPInit.h.

References evaluateInsertion().

Referenced by createNewRoute().

bool eoVRPInit::evaluateInsertion	(	Route &	_route,
		unsigned	_newClient,
		int	_afterClient,
		double &	_cost
	)			`[inline, private]`

Evaluates the feasibility and the cost of inserting a new client in a given subroute.

Given a subroute, this method tries evaluates if it is possible to insert a client in a position. It will return the cost of the resulting route if this insertion is possible.

Parameters:

	_route	The route where we are trying to insert a new client.
	_newClient	The client we are trying to insert.
	_afterClient	The position of insertion.
	_cost	A return value. The cost of inserting the given client at the given position.

Returns:: True if the new insertion is possible. False otherwise.

Definition at line 308 of file eoVRPInit.h.

References eoVRPUtils::clients, eoVRPUtils::distance(), and eoVRPUtils::getTimeWindow().

Referenced by selectBestInsertion().

unsigned eoVRPInit::selectFarthestClientAsSeed	(	const std::vector< int > &	_unvisited,
		int	_unvisitedIdx
	)			`[inline, private]`

Selects the farthest client as seed for a new route.

Parameters:

	_unvisited	Vector of unvisited and thus available clients for constructing the new route.
	_unvisitedIdx	Position of the last univisted client in _unvisited vector.

Returns:: The position of the client farthest from the depot.

Definition at line 472 of file eoVRPInit.h.

References eoVRPUtils::distance().

unsigned eoVRPInit::selectCheapestClient	(	const std::vector< int > &	_unvisited,
		int	_unvisitedIdx,
		bool	_seedCheckingOverride
	)			`[inline, private]`

Selects the cheapest client as seed for a new route.

Parameters:

	_unvisited	Vector of unvisited and thus available clients for constructing the new route.
	_unvisitedIdx	Position of the last univisted client in _unvisited vector.
	_seedCheckingOverride	If true, it overrides the seed checking mecanism.

Returns:: The position of the cheapest client.

Definition at line 498 of file eoVRPInit.h.

References eoVRPUtils::clients, eoVRPUtils::distance(), eoRng::flip(), mSeedsUsed, and eoVRPUtils::polarAngle().

unsigned eoVRPInit::selectBestClientAsSeed	(	const std::vector< int > &	_unvisited,
		int	_unvisitedIdx,
		bool	_seedCheckingOverride
	)			`[inline, private]`

Selects the best (the "hardest" one) client as seed for a new route.

Parameters:

	_unvisited	Vector of unvisited and thus available clients for constructing the new route.
	_unvisitedIdx	Position of the last univisted client in _unvisited vector.
	_seedCheckingOverride	If true, it overrides the seed checking mecanism.

Returns:: The position of the best client.

Definition at line 532 of file eoVRPInit.h.

References eoVRPUtils::clients, eoVRPUtils::distance(), eoRng::flip(), mSeedsUsed, and eoRng::uniform().

Referenced by createNewRoute().

void eoVRPInit::RandomInitializationNoCheck ( eoVRP & _gen ) [inline, private]

Random initializer.

Initializes a genotype using a random initializer.

Parameters:

_gen

Generally a genotype that has been default-constructed. Whatever it contains will be lost.

Definition at line 569 of file eoVRPInit.h.

References eoVRPUtils::clients, and eoRng::random().

eoVRPInit Class Reference

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation


Public Member Functions
	eoVRPInit ()
	Default constructor: nothing to do here.
void	operator() (eoVRP &_gen)
	Functor member.
Private Member Functions
void	HeuristicInitialization (eoVRP &_gen)
	Heuristic initializer.
bool	createNewRoute (std::vector< int > &_unvisited, int &_unvisitedIdx, bool _seedCheckingOverride, Route &_route)
	Creates a new route.
bool	selectBestInsertion (std::vector< int > &_unvisited, unsigned _unvisitedIdx, Route &_route, unsigned &_nextClient, Route::iterator &_it)
	Selects the best client and the best position for its insertion in a given route.
bool	evaluateInsertion (Route &_route, unsigned _newClient, int _afterClient, double &_cost)
	Evaluates the feasibility and the cost of inserting a new client in a given subroute.
unsigned	selectFarthestClientAsSeed (const std::vector< int > &_unvisited, int _unvisitedIdx)
	Selects the farthest client as seed for a new route.
unsigned	selectCheapestClient (const std::vector< int > &_unvisited, int _unvisitedIdx, bool _seedCheckingOverride)
	Selects the cheapest client as seed for a new route.
unsigned	selectBestClientAsSeed (const std::vector< int > &_unvisited, int _unvisitedIdx, bool _seedCheckingOverride)
	Selects the best (the "hardest" one) client as seed for a new route.
void	RandomInitializationNoCheck (eoVRP &_gen)
	Random initializer.
Private Attributes
unsigned	mSeedsUsedCount
	Number of clients already used as seeds.
std::vector< bool >	mSeedsUsed
	Vector storing if a client has been used as a seed or not.