Temporal decomposition

IBM ILOG Dispatcher User's Manual > Developing Dispatcher Applications > Designing Dispatcher Models > Decompose the problem > Temporal decomposition

Temporal decomposition

INDEX

PREVIOUS NEXT

To show how to use temporal decomposition, you will solve a technician dispatching problem. As in Chapter 13, Dispatching Technicians, you will model and solve this problem using RoutingModel and RoutingSolver classes. There are 5 technicians who must perform 50 visits over 3 days. There are 5 different skill levels, depending on technician. Certain visits require technicians of a certain skill level. A SkillCosts class is used to model costs and maximize the quality of service. If a technician type is well suited to performing a certain visit, then the cost for that technician/visit pair should be low. If a technician type is not well suited to performing a visit, the cost for that technician/visit pair should be high.

You will also create a Day class to create submodels of the problem for each of the 3 days. One model, an instance of IloModel, per day is maintained. Each of these models contains the dimensions of the problem and the technicians assigned to work that day. A model of the whole problem, containing the day submodels, is also maintained.

The solution process is iterative. Each day submodel is improved and then the whole problem is improved. This latter phase is one that can cause visits to migrate from one day to another. In other words, moves can be performed that cause a technician to perform a visit on a different day. When the next iteration to improve days begins, a synchronization needs to be performed. During this synchronization, the submodels are updated with the changes made during the improvement stage of the whole problem.

Only the parts of this example that are changed from Chapter 13, Dispatching Technicians are shown here. You can view the complete program and output online in the YourDispatcherHome/examples/src/technicianDispatching.cpp file.

Declare the Day class

The code for the declaration of the Day class follows:

class Day {
private:
  IloEnv             _env;
  IloNode            _node;
  IloInt             _nbOfTechnicians;
  IloInt             _capacity;
  IloNum             _openTime;
  IloNum             _closeTime;
  IloVehicleArray    _technicians;
  IloVisitArray      _visits;
  IloModel           _model;
  IloNHood           _nhood;
  IloMetaHeuristic   _mh;
  IloInt             _index;
  char *             _name;

public:
  Day(IloEnv env,
      IloInt index,
      const char *name,
      IloNode node,
      IloInt nbOfTechnicians,
      IloInt capacity,
      IloNum openTime,
      IloNum closeTime);
  ~Day();

  const char* getName() const { return _name;}
  void add(IloExtractable ex) { _model.add(ex); }
  void add(IloVehicle technician) {
    _technicians.add(technician);
    _model.add(technician);
  }
  IloInt getIndex() const { return _index; }
  IloModel getModel() const { return _model; }
  IloVehicleArray getTechnicians() const { return _technicians; }
  IloBool improve(IloSolver solver, IloRoutingSolution rs, IloGoal g);
  void fillModel(IloRoutingSolution rs);

  void createTechnicians(IloDimension2 time, IloDimension1 skillPenalty);
  IloVehicle createOneTechnician (IloInt technicianIndex,
                                  IloDimension2 time,
                                  IloDimension1 skillPenalty);
};

Define the Day constructor

A day is built from an instance of IloEnv and is given a name name:

Day::Day (IloEnv env,
          IloInt index,
          const char *name,
          IloNode node,
          IloInt nbOfTechnicians,
          IloInt capacity,
          IloNum openTime,
          IloNum closeTime)
  : _env(env),
    _node(node),
    _nbOfTechnicians(nbOfTechnicians),
    _capacity(capacity),
    _openTime(openTime),
    _closeTime(closeTime),
    _technicians(env),
    _visits(env),
    _model(env),
    _index(index) {

In order to improve solutions for this day, a neighborhood _nhood and a greedy metaheuristic _mh are created. As the subproblem of improving the solution for a single day is likely to be relatively small, five move operators are used in the neighborhood.

  _nhood = IloTwoOpt(env)
         + IloOrOpt(env)
         + IloRelocate(env)
         + IloCross(env)
         + IloExchange(env)
       //+ IloRelocateTours(env)
         ;
  _mh = IloImprove(env);

A day destructor is also defined:

Day::~Day() {
  _nhood.end();
  _mh.end();
  _technicians.end();
  _visits.end();
  _env.getImpl()->free(_name, sizeof(char) * (strlen(_name) + 1));
}

Define the Day::Improve function

You define a method improve that is used for improving the solution rs passed as an argument. A solver solver and a goal g to be executed at each move are also passed as parameters. The number of moves made is returned. First, the neighborhood and greedy metaheuristic are reset. Then, the improvement goal is created using IloSingleMove. An improvement loop is then entered, which stops when no move can improve the cost of the current solution. Finally, the number of moves made is returned.

IloBool Day::improve(IloSolver solver, IloRoutingSolution rs, IloGoal g) {
  _nhood.reset();
  _mh.reset();
  IloGoal improve = IloSingleMove(_env, rs, _nhood, _mh, g);
  solver.out() << "  Optimizing day " << getName() << " "
               << rs.getSolution().getObjectiveValue() << flush;
  IloBool moves = 0;
  while (solver.solve(improve)) ++moves;
  solver.out() << " ---> " << rs.getSolution().getObjectiveValue() << endl;
  return (moves>0);
}

Define the Day::fillModel function

The class Day also requires the ability to synchronize its internal model with a routing solution. To perform this you first empty the model of the visit models which previously comprised the model. You then scan the solution for the technicians who are working on this day, and for each one, find out which visits are made by these technicians. These visits (or more accurately, the models pertaining to these visits) must then be placed in the day model. You keep track of which visits are in the model in the array _visits.

void Day::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 < _technicians.getSize(); i++) {
    for (IloRoutingSolution::RouteIterator r(rs, _technicians[i]); r.ok(); ++r) 
{
      IloVisit visit = *r;
      if ( !visit.isFirstVisit() && !visit.isLastVisit() ) {
        _visits.add(visit);
        _model.add( (IloModelI*)visit.getObject() );
      }
    }
  }
}

Define the Day::createOneTechnician function

You add a function to create a technician associated to the day. The technicians have first and last visits each day. You add side constraints that the technicians must leave the depot after it opens and return to the depot before it closes. You set the cost of the technician. The cost of each technician is directly proportional to the dimension time and the skillPenalty.

Define the Day::createTechnicians function

You create a function that will be called by RoutingModel::createDays. This loop will be used to create the technicians assigned to work each day.

void Day::createTechnicians(IloDimension2 time,
                            IloDimension1 skillPenalty) {
  for (IloInt v=0; v < _nbOfTechnicians; v++) {
    createOneTechnician(v, time, skillPenalty);
  }
}

Define the RoutingModel::createDays function

You use Concert Technology's csv reader functionality to input day data from csv files. For each of the days, you get the number of technicians (nbOfTechnicians), the depot (nodeName), and its opening and closing times (openTime and closeTime). An array of pointers to class type Day are created. This array is then populated by a loop that creates the days. For each day, the function Day::createTechnicians is called to create the technicians associated with each day and the model containing all dimensions _dimModel is added to the day model. Finally, each day model is added to the model of the whole problem _mdl.

void RoutingModel::createDays(const char* daysFileName) {
  IloCsvReader dayReader(_env, daysFileName);
  _nbOfDays = dayReader.getNumberOfItems();
  _days = new (_env) Day* [_nbOfDays];

  IloInt dayIndex = 0;
  for (IloCsvReader::LineIterator it(dayReader); it.ok(); ++it, ++dayIndex) {
    IloCsvLine line = *it;
    const char* name = line.getStringByHeader("name");
    char * nodeName  = line.getStringByHeader("nodeName");
    IloNum openTime   = line.getFloatByHeader("openTime");
    IloNum closeTime  = line.getFloatByHeader("closeTime");
    IloInt nbOfTechnicians = line.getIntByHeader("nbOfTechnicians");
    IloInt capacity   = line.getIntByHeader("capacity");

    IloNode depot = IloNode::Find(_env, nodeName);

    Day* day = new (_env) Day(_env,
                              dayIndex,
                              name,
                              depot,
                              nbOfTechnicians,
                              capacity,
                              openTime,
                              closeTime);
    _days[dayIndex] = day;
  }
  dayReader.end();

  IloInt d;
  for (d=0; d < _nbOfDays; ++d) {
    Day* day = _days[d];
    day->createTechnicians(_time, _skillPenalty);
    day->add(_dimModel);
    _mdl.add(day->getModel());
  }

}

Define the createSkillCostFunction

The function createSkillCostFunction creates the vehicle array technicians. The IloCsvReader instance csvVisitSkillsReader reads the skills required at each customer visit; csvTechSkillsReader reads the skill level of each technician; and csvSkillCostsReader reads the cost for each technician skill type to perform a visit to a customer site.

The next section of createSkillCostFunction creates an array of the cost for each visit, named skillCosts. To create this array, the visit skill required for each visit (VisitSkillName) is read from a csv file. The cost to make this visit with the various techSkill levels is read with csvSkillCostsReader as an IloCsvLine costline. Then the value in costline corresponding to the appropriate TechSkillName is stored in the array skillCosts.

Finally, the IloVehicleToNumFunction constructor associates the values of the array skillCosts to the vehicle/technicians of the array technicians.

IloVehicleToNumFunction
SkillCosts::createSkillCostFunction(Day* day,
                                    IloVisit visit,
                                    IloCsvReader csvVisitSkillsReader,
                                    IloCsvReader csvTechSkillsReader,
                                    IloCsvReader csvSkillCostsReader) {
  IloVehicleArray technicians = day->getTechnicians();
  IloInt size = technicians.getSize();
  IloNumArray skillCosts(_env, size);
  IloCsvLine line1 = csvVisitSkillsReader.getLineByKey(1, visit.getName());
  char* skillName = line1.getStringByHeader("VisitSkillName");
  IloCsvLine costline = csvSkillCostsReader.getLineByKey(1, skillName);
  for (IloInt  i = 0; i < size; i++) {
    IloVehicle technician = technicians[i];
    IloCsvLine line2 = csvTechSkillsReader.getLineByKey(1, 
technician.getName());
    char * techSkillName = line2.getStringByHeader("TechSkillName");
    skillCosts[i] = costline.getFloatByHeader(techSkillName);
  }
  return IloVehicleToNumFunction(_env, technicians, skillCosts, 0);
}

Define the RoutingSolver::improveDays function

If a first solution is found, the solution is improved using local search. You iterate over all days, using Day::fillModel to populate each model. You then update the cost of the global solution according to the model of this day. You use Day::improve to attempt to reduce the cost of the routing for this day. Finally, the solution is synchronized with the global model.

Define the RoutingSolver::improvePlan function

After the routing for all days has been improved independently, the routing for the problem as a whole is improved. After resetting the neighborhood and greedy metaheuristic, an improvement loop is entered to improve the cost of all days using the goal _move. If there was some improvement, then you go back to an independent improvement of each day. Otherwise, you leave the main improvement loop.

PREVIOUS NEXT