How to assign task, resources to trips

Question

In a scheduling problem I want to assign the resources to tasks, each task has earliest start date, latest start date and duration. Also each resource has fixed number of available hours in a day. The problem is resource and task are located at different locations and each task have their own time window. A resource can make a trip to a location and complete certain number of tasks and come back. Later on it can make second trip and complete certain number tasks. For each hour (worktime, wait time) spent at destination location there is a cost. What tasks shall I assign in a trip so that there is minimum cost of assignment and when shall a resource start a trip ?

Answer 1

As pointed out by A.Omidi in the comment above, your problem is a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). It can be naturally modeled by following a list-based modeling approach. This is a modeling approach offered by LocalSolver, which is different from traditional solvers. Note that LocalSolver is commercial software. Nevertheless, it is free for faculty and students.

Below is the code snippet to model the classical CVRPTW problem in LSP, the modeling language that comes with LocalSolver:

function model() {
  customersSequences[k in 1..nbTrucks] <- list(nbCustomers);

  // All customers must be visited by the trucks
  constraint partition[k in 1..nbTrucks](customersSequences[k]);

  for[k in 1..nbTrucks] {
    local sequence <- customersSequences[k];
    local c <- count(sequence);

    // A truck is used if it visits at least one customer
    truckUsed[k] <- c > 0;

    // The quantity needed in each route must not exceed the truck capacity
    routeQuantity[k] <- sum(0..c-1, i => demands[sequence[i]]);
    constraint routeQuantity[k] <= truckCapacity;

    endTime[k] <- array(0..c-1, (i, prev) => max(earliestStart[sequence[i]],
      i == 0 ?
      distanceWarehouse[sequence[0]] :
      prev + distanceMatrix[sequence[i-1]][sequence[i]]) + serviceTime[sequence[i]]);

    homeLateness[k] <- truckUsed[k] ?
      max(0, endTime[k][c - 1] + distanceWarehouse[sequence[c - 1]] - maxHorizon) :
      0;

    // Distance traveled by truck k
    routeDistances[k] <- sum(1..c-1,
      i => distanceMatrix[sequence[i-1]][sequence[i]]) + (truckUsed[k] ?
      distanceWarehouse[sequence[0]] + distanceWarehouse[sequence[c-1]] :
      0);

    lateness[k] <- homeLateness[k] + sum(0..c-1,
      i => max(0, endTime[k][i] - latestEnd[sequence[i]]));
  }

  // Total lateness, must be 0 for a solution to be valid
  totalLateness <- sum[k in 1..nbTrucks](lateness[k]);

  nbTrucksUsed <- sum[k in 1..nbTrucks](truckUsed[k]);

  // Total distance traveled
  totalDistance <- sum[k in 1..nbTrucks](routeDistances[k]);

  minimize totalLateness;
  minimize nbTrucksUsed;
  minimize totalDistance;
}

The complete LSP code and the corresponding codes for Python, Java, C#, and C++ are given here: https://www.localsolver.com/docs/last/exampletour/vrptw.html.

Having followed this modeling approach, LocalSolver finds quality solutions (optimality gap less than 5%) in a few minutes for CVRPTW instances with hundreds of customers to visit. LocalSolver embeds and combines neighborhood search, constraint programming, and mixed-integer linear programming techniques under the hood to get such results.

For an introduction to the list-based modeling approach for combinatorial optimization, have a look at https://www.localsolver.com/docs/last/advancedfeatures/collectionvariables.html.