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
    Commented Mar 18, 2021 at 17:20

1 Answer 1

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 Hexaly, which is different from traditional solvers. Note that Hexaly is commercial software. Nevertheless, it is free for faculty and students.

Below is the code snippet to model the classical CVRPTW problem in Hexaly Modeler:

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 Hexaly Modeler code and the corresponding Python, Java, C#, and C++ codes are here: https://www.hexaly.com/docs/last/exampletour/vrptw.html.

Following this modeling approach, Hexaly finds quality solutions (optimality gap less than 1%) for CVRPTW instances with thousands of customers to visit in a few minutes.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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