# How to assign task, resources to trips

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 ?

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

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() {

// All customers must be visited by the trucks

for[k in 1..nbTrucks] {
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.