The complete program for mpdpd.cpp follows. You can also view it online in the file YourDispatcherHome/examples/src/mdpdp.cpp.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/mdpdp.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
class Depot {
private:
IloEnv _env;
IloNode _node;
IloInt _nbOfTrucks;
IloInt _capacity;
IloNum _openTime;
IloNum _closeTime;
IloVehicleArray _vehicles;
IloVisitArray _visits;
IloModel _model;
IloNHood _nhood;
IloMetaHeuristic _mh;
public:
Depot(IloEnv env, const char *name, IloNum x, IloNum y,
IloInt nbOfTrucks, IloInt capacity,
IloNum openTime, IloNum closeTime
);
~Depot();
const char* getName() const { return _node.getName();}
void add(IloExtractable ex) { _model.add(ex); }
void add(IloVehicle vehicle) { _vehicles.add(vehicle); _model.add(vehicle); }
IloModel getModel() const { return _model; }
IloBool improve(IloSolver solver, IloRoutingSolution rs, IloGoal g);
void fillModel(IloRoutingSolution rs);
void createVehicles(IloDimension2 time, IloDimension2 length, IloDimension1 weight);
IloVehicle createOneVehicle(IloInt vehicleIndex,
IloDimension2 time,
IloDimension2 length,
IloDimension1 weight);
};
Depot
::Depot(IloEnv env, const char *name, IloNum x, IloNum y,
IloInt nbOfTrucks, IloInt capacity,
IloNum openTime, IloNum closeTime
)
: _env(env),
_node(env, x, y, 0, name),
_nbOfTrucks(nbOfTrucks),
_capacity(capacity),
_openTime(openTime),
_closeTime(closeTime),
_vehicles(env),
_visits(env),
_model(env)
{
_nhood = IloTwoOpt(env) + IloOrOpt(env) + IloRelocate(env) +
IloCross(env) + IloExchange(env)
//+ IloRelocateTours(env)
;
_mh = IloImprove(env);
}
Depot::~Depot() {
_nhood.end();
_mh.end();
_vehicles.end();
_visits.end();
}
IloBool Depot::improve(IloSolver solver, IloRoutingSolution rs, IloGoal g) {
_nhood.reset();
_mh.reset();
IloGoal improve = IloSingleMove(_env, rs, _nhood, _mh, g);
solver.out() << " Optimizing depot " << getName() << " "
<< rs.getSolution().getObjectiveValue() << flush;
IloBool moves = 0;
while (solver.solve(improve)) ++moves;
solver.out() << " ---> " << rs.getSolution().getObjectiveValue() << endl;
return (moves>0);
}
void Depot::fillModel(IloRoutingSolution rs) {
IloInt i;
for (i = 0; i < _visits.getSize(); i++)
_model.remove((IloModelI *)_visits[i].getObject());
_visits.end();
_visits = IloVisitArray(_env);
for (i = 0; i < _vehicles.getSize(); i++) {
for (IloRoutingSolution::RouteIterator r(rs, _vehicles[i]); r.ok(); ++r) {
IloVisit visit = *r;
if ( !visit.isFirstVisit() && !visit.isLastVisit() ) {
_visits.add(visit);
_model.add( (IloModelI*)visit.getObject() );
}
}
}
}
void Depot::createVehicles(IloDimension2 time,
IloDimension2 length,
IloDimension1 weight) {
for (IloInt v=0; v < _nbOfTrucks; ++v) {
IloVehicle vehicle = createOneVehicle(v, time, length, weight);
_vehicles[v] = vehicle;
}
}
IloVehicle Depot::createOneVehicle(IloInt vehicleIndex,
IloDimension2 time,
IloDimension2 length,
IloDimension1 weight) {
char namebuf[128];
const char* depotName = getName();
sprintf(namebuf, "Truck %ld leaving %s", vehicleIndex, depotName);
IloVisit first(_node, namebuf);
sprintf(namebuf, "Truck %ld returning to %s", vehicleIndex, depotName);
IloVisit last (_node, namebuf);
sprintf(namebuf, "Vehicle %ld of Depot %s", vehicleIndex, getName());
IloVehicle vehicle(first, last, namebuf);
vehicle.setCost(length, 1.0);
vehicle.setCapacity(weight, _capacity);
add(vehicle);
add(first.getCumulVar(time) >= _openTime);
add(last.getCumulVar(time) <= _closeTime);
last.getCumulVar(weight).setBounds(0,0);
first.getCumulVar(length).setBounds(0,0);
first.getDelayVar(length).setBounds(0,0);
first.getWaitVar(length).setBounds(0,0);
last.getDelayVar(length).setBounds(0,0);
last.getWaitVar(length).setBounds(0,0);
vehicle.setObject(this);
return vehicle;
}
class RoutingModel {
IloEnv _env;
IloModel _mdl;
IloModel _dimModel;
IloDistance _distance;
IloDimension2 _time;
IloDimension2 _length;
IloDimension1 _weight;
const char* _depotPath; // "../../../examples/data/mdvrp/depots.csv";
const char* _visitPath; // "../../../examples/data/mdvrp/vrp100.csv";
const char* _nodePath; // "../../../examples/data/mdvrp/node100.csv";
IloInt _nbOfDepots;
Depot** _depots;
protected:
void createDimensions();
void createNodes (const char* nodePath);
void createDepots(const char* depotPath);
void createVisits(const char* orderPath);
public:
RoutingModel(IloEnv env);
~RoutingModel() {}
IloEnv getEnv() const { return _env; }
IloModel getModel() const { return _mdl; }
IloInt getNumberOfDepots() const { return _nbOfDepots;}
Depot* getDepot(IloInt d) const {
assert( d >= 0 );
assert( d < _nbOfDepots);
return _depots[d];
}
void parse(int argc, char** argv);
void init();
void createModel();
};
RoutingModel::RoutingModel(IloEnv env)
: _env(env),
_depotPath("../../../examples/data/mdpdp/depots.csv"),
_visitPath("../../../examples/data/mdpdp/vrp100.csv"),
_nodePath ("../../../examples/data/mdpdp/node100.csv"),
_nbOfDepots(0),
_depots(0)
{
}
void RoutingModel::parse(int argc, char** argv) {
if ( argc >= 4 ) {
_depotPath = argv[1];
_visitPath = argv[2];
_nodePath = argv[3];
}
}
void RoutingModel::createModel() {
_mdl = IloModel(_env);
createDimensions();
createNodes(_nodePath);
createDepots(_depotPath);
createVisits(_visitPath);
}
void RoutingModel::createDimensions() {
_dimModel = IloModel(_env);
_distance = IloDistance(_env, IloEuclidean);
_weight = IloDimension1(_env, "weight");
_dimModel.add(_weight);
_time = IloDimension2(_env, _distance , "time");
_dimModel.add(_time);
_length = IloDimension2(_env, _distance , "distance");
_dimModel.add(_length);
_mdl.add(_dimModel);
}
void RoutingModel::createNodes(const char* nodePath) {
IloCsvReader nodeReader(_env, nodePath);
for (IloCsvReader::LineIterator it(nodeReader); it.ok(); ++it) {
IloCsvLine line = *it;
const char* name = line.getStringByHeader("name");
IloNode node(_env,
line.getFloatByHeader("x"),
line.getFloatByHeader("y"),
0, // no Z coordinate here.
name);
node.setKey(name);
}
nodeReader.end();
}
void RoutingModel::createDepots(const char* depotPath) {
IloCsvReader depotReader(_env, depotPath);
_nbOfDepots = depotReader.getNumberOfItems();
_depots = new (_env) Depot* [ _nbOfDepots ];
IloInt depotIndex = 0;
for (IloCsvReader::LineIterator it(depotReader); it.ok(); ++it, ++depotIndex) {
IloCsvLine line = *it;
const char* name = line.getStringByHeader("name");
IloNum x = line.getFloatByHeader("x");
IloNum y = line.getFloatByHeader("y");
IloNum openTime = line.getFloatByHeader("openTime");
IloNum closeTime = line.getFloatByHeader("closeTime");
IloInt nbOfTrucks = line.getIntByHeader("nbOfTrucks");
IloInt capacity = line.getIntByHeader("capacity");
Depot* depot =
new (_env) Depot(_env, name, x, y, nbOfTrucks, capacity, openTime, closeTime);
_depots[ depotIndex ] = depot;
}
depotReader.end();
IloInt d;
for (d=0; d < _nbOfDepots; ++d) {
Depot* depot = _depots[d];
depot->createVehicles(_time, _length, _weight);
depot->add(_dimModel);
_mdl.add(depot->getModel());
}
}
void RoutingModel::createVisits(const char* visitPath) {
IloCsvReader orderReader(_env, visitPath);
IloCsvReader::LineIterator it(orderReader);
while ( it.ok() ) {
IloCsvLine line = *it;
//read visit data from files
char * pickupVisitName = line.getStringByHeader("pickup");
char * pickupNodeName = line.getStringByHeader("pickupNode");
char * deliveryVisitName = line.getStringByHeader("delivery");
char * deliveryNodeName = line.getStringByHeader("deliveryNode");
IloNum quantity = line.getFloatByHeader("quantity");
IloNum pickupMinTime = line.getFloatByHeader("pickupMinTime");
IloNum pickupMaxTime = line.getFloatByHeader("pickupMaxTime");
IloNum deliveryMinTime = line.getFloatByHeader("deliveryMinTime");
IloNum deliveryMaxTime = line.getFloatByHeader("deliveryMaxTime");
IloNum dropTime = line.getFloatByHeader("dropTime");
IloNum pickupTime = line.getFloatByHeader("pickupTime");
//read data nodes from the file nodes.csv and creat pickup and delivery nodes
IloNode pickupNode = IloNode::Find(_env, pickupNodeName);
IloNode deliveryNode = IloNode::Find(_env, deliveryNodeName);
//create and add pickup and delivery visits
IloModel pickupModel(_env);
IloModel deliveryModel(_env);
IloVisit pickup(pickupNode, pickupVisitName);
pickupModel.add(pickup.getDelayVar(_time) == pickupTime);
pickupModel.add(pickup.getTransitVar(_weight) == quantity);
pickupModel.add(pickupMinTime <= pickup.getCumulVar(_time) <= pickupMaxTime);
pickupModel.add(pickup);
pickup.setObject( (IloAny)pickupModel.getImpl() );
pickup.getDelayVar(_length).setBounds(0,0);
pickup.getWaitVar(_length).setBounds(0,0);
IloVisit delivery(deliveryNode, deliveryVisitName);
deliveryModel.add(delivery.getDelayVar(_time) == dropTime);
deliveryModel.add(delivery.getTransitVar(_weight) == -quantity);
deliveryModel.add(deliveryMinTime <= delivery.getCumulVar(_time) <= deliveryMaxTime);
deliveryModel.add(delivery);
delivery.getDelayVar(_length).setBounds(0,0);
delivery.getWaitVar(_length).setBounds(0,0);
//add pickup and delivery order constraint
pickupModel.add( IloOrderedVisitPair(_env, pickup, delivery) );
delivery.setObject( (IloAny)deliveryModel.getImpl() );
_mdl.add( pickupModel );
_mdl.add( deliveryModel );
++it;
}
orderReader.end();
}
class RoutingSolver {
RoutingModel& _routing;
IloModel _mdl;
IloSolver _solver;
IloDispatcher _dispatcher;
IloRoutingSolution _solution;
IloGoal _instantiateCost;
IloGoal _restoreSolution;
IloGoal _fsGoal;
IloNHood _nhood;
IloMetaHeuristic _greedy;
IloGoal _move;
public:
RoutingSolver(RoutingModel& routingModel);
~RoutingSolver() {}
IloEnv getEnv() const { return _mdl.getEnv();}
void syncSolution(IloModel mdl, IloSolution s, IloGoal g);
void syncSolution();
IloBool findFirstSolution();
IloBool improveDepots();
IloBool improvePlan();
void printInformation() const;
};
RoutingSolver::RoutingSolver(RoutingModel& routingModel)
: _routing( routingModel),
_mdl(routingModel.getModel()),
_solver(routingModel.getModel()),
_dispatcher(_solver),
_solution(routingModel.getModel())
{
IloEnv env = getEnv();
_instantiateCost =
IloDichotomize(env, _dispatcher.getCostVar(), IloFalse);
_restoreSolution = IloRestoreSolution(env, _solution);
_fsGoal = IloNearestAdditionGenerate(env);
_nhood = IloRelocate(env) + IloExchange(env);
_greedy = IloImprove(env);
}
void RoutingSolver::printInformation() const {
_solver.printInformation();
_dispatcher.printInformation();
_solver.out() << "===============" << endl
<< "Cost : " << _dispatcher.getTotalCost() << endl
<< "Number of vehicles used : "
<< _dispatcher.getNumberOfVehiclesUsed() << endl
<< "Solution : " << endl
<< _dispatcher << endl;
}
// Solving : find first solution
IloBool RoutingSolver::findFirstSolution() {
if (!_solver.solve(_fsGoal && _instantiateCost)) {
_solver.error() << "Infeasible Routing Plan" << endl;
return IloFalse;
}
_solution.store(_solver);
_solver.out() << "First solution with cost: "
<< _solution.getObjectiveValue()
<< endl;
return IloTrue;
}
IloBool RoutingSolver::improveDepots() {
IloEnv env = getEnv();
_move =
IloSingleMove(env, _solution, _nhood, _greedy, _instantiateCost);
_solver.out() << endl << "Improvement loop" << endl;
_solver.out() << "================" << endl;
IloBool improved = IloTrue;
IloInt nbOfDepots = _routing.getNumberOfDepots();
improved = IloFalse;
for (IloInt d = 0; d < nbOfDepots; ++d) {
Depot* depot = _routing.getDepot(d);
depot->fillModel(_solution);
syncSolution(depot->getModel(), _solution, _instantiateCost);
if ( depot->improve(_solver, _solution, _instantiateCost) ) {
improved = IloTrue;
}
}
// sync back to full model.
syncSolution(_mdl, _solution, _instantiateCost);
return improved;
}
IloBool RoutingSolver::improvePlan() {
_solver.out() << "Optimizing plan "
<< _solution.getSolution().getObjectiveValue()
<< flush;
_nhood.reset();
_greedy.reset();
IloInt nbImproved = 0;
while ( _solver.solve(_move) ) { ++nbImproved;}
_solver.out() << " ---> "
<< _solution.getSolution().getObjectiveValue() << endl;
return ( nbImproved > 0 );
}
void RoutingSolver::syncSolution(IloModel mdl, IloSolution s, IloGoal g) {
_solver.extract(mdl);
if ( !_solver.solve( IloRestoreSolution( _solver.getEnv(), s) && g))
_solver.out() << "Synchronization failed" << endl;
else
s.store(_solver);
}
void RoutingSolver::syncSolution() {
syncSolution(_mdl, _solution, _instantiateCost);
}
int main(int argc, char* argv[]) {
IloEnv env;
try {
RoutingModel routingModel(env);
routingModel.parse(argc, argv);
routingModel.createModel();
RoutingSolver rsolver(routingModel);
if ( rsolver.findFirstSolution() ) {
IloBool improved = IloTrue;
do {
improved =
rsolver.improveDepots() && rsolver.improvePlan();
} while ( improved );
}
rsolver.syncSolution();
rsolver.printInformation();
} catch (IloException& ex) {
env.out() << "Error: " << ex << endl;
}
env.end();
return 0;
}
PREVIOUS
NEXT