3
$\begingroup$

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 ?

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ The problem you mentioned sounds like a variant of VRP that is CVRPTW (capacitated vehicle routing) in which the number of capacitated resources should be travelling between the number of distinctions in the specific time window. Also, if you are willing to schedule only one resource it can be reduced to a TSPTW or TSP with job processing time. Do you try that? $\endgroup$ – A.Omidi Mar 18 at 17:20
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.