how to minimize each vehicle time in vrp with or-tools

[AlirezaTheH]

i want minimize network time in other words: each vehicle time should be minimized as possible
1- this means force all vehicle to service locations
2- and balance number of locations serviced per vehicle
3- and minimizes the time the last vehicle will arrive to its end node
@daniel-j-h what you said about forcing all vehicle works fine but others not working at all
do you have any idea to do number 3?

[daniel-j-h]

Number three is ticketed in #12.

I don't have time to run this out - if you want to give it a try it mainly should be a matter of adding a new parameter and then passing it through to the solver (as described in the ticket).

[AlirezaTheH]

i actually used the #12 and the makespan not yet minimized
here is my whole code in python:

import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2


def distance(x1, y1, x2, y2):
    dist = math.ceil(math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2))

    return dist


class CreateDistanceCallback(object):
    """Create callback to calculate distances between points."""

    def __init__(self, locations):
        """Initialize distance array."""
        size = len(locations)
        self.matrix = {}

        for from_node in range(size):
            self.matrix[from_node] = {}
            for to_node in range(size):
                if from_node == size - 1 or to_node == size - 1:
                    # Define the distance from the depot to any node to be 0.
                    self.matrix[from_node][to_node] = 0
                else:
                    x1 = locations[from_node][0]
                    y1 = locations[from_node][1]
                    x2 = locations[to_node][0]
                    y2 = locations[to_node][1]
                    self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

    def Distance(self, from_node, to_node):
        return int(self.matrix[from_node][to_node])


# Demand callback
class CreateDemandCallback(object):
    """Create callback to get demands at each location."""

    def __init__(self, demands):
        self.matrix = demands

    def Demand(self, from_node, to_node):
        return self.matrix[from_node]


# Service time (proportional to demand) callback.
class CreateServiceTimeCallback(object):
    """Create callback to get time windows at each location."""

    def __init__(self, demands, time_per_demand_unit):
        self.matrix = demands
        self.time_per_demand_unit = time_per_demand_unit

    def ServiceTime(self, from_node, to_node):
        return int(self.matrix[from_node] * self.time_per_demand_unit)


# Create the travel time callback (equals distance divided by speed).
class CreateTravelTimeCallback(object):
    """Create callback to get travel times between locations."""

    def __init__(self, dist_callback, speed):
        self.dist_callback = dist_callback
        self.speed = speed

    def TravelTime(self, from_node, to_node):
        travel_time = self.dist_callback(from_node, to_node) / self.speed
        return int(travel_time)


# Create total_time callback (equals service time plus travel time).
class CreateTotalTimeCallback(object):
    """Create callback to get total times between locations."""

    def __init__(self, service_time_callback, travel_time_callback):
        self.service_time_callback = service_time_callback
        self.travel_time_callback = travel_time_callback

    def TotalTime(self, from_node, to_node):
        service_time = self.service_time_callback(from_node, to_node)
        travel_time = self.travel_time_callback(from_node, to_node)
        return service_time + travel_time


def main():
    # Create the data.
    data = create_data_array()
    locations = data[0]
    demands = data[1]
    num_locations = len(locations)
    start_locations = [0, 1]
    end_locations = [10, 10]
    num_vehicles = 2

    # Create routing model.
    if num_locations > 0:
        routing = pywrapcp.RoutingModel(num_locations, num_vehicles, start_locations, end_locations)
        search_parameters = pywrapcp.RoutingModel_DefaultSearchParameters()

        # Callback to the distance function.
        dist_between_locations = CreateDistanceCallback(locations)
        dist_callback = dist_between_locations.Distance
        routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

        # Add time dimension.
        time_per_demand_unit = 5
        fix_start_cumul_to_zero = True
        horizon = 500
        time = "Time"
        speed = 1

        service_times = CreateServiceTimeCallback(demands, time_per_demand_unit)
        service_time_callback = service_times.ServiceTime

        travel_times = CreateTravelTimeCallback(dist_callback, speed)
        travel_time_callback = travel_times.TravelTime

        total_times = CreateTotalTimeCallback(service_time_callback, travel_time_callback)
        total_time_callback = total_times.TotalTime

        routing.AddDimension(total_time_callback,  # total time function callback
                             horizon,
                             horizon,
                             fix_start_cumul_to_zero,
                             time)

        for vehicle in range(routing.vehicles()):
            routing.AddVariableMinimizedByFinalizer(routing.CumulVar(routing.End(vehicle), time))

        for vehicle_nbr in range(num_vehicles):
            start_var = routing.NextVar(routing.Start(vehicle_nbr))
            for node_index in range(routing.Size(), routing.Size() + routing.vehicles()):
                start_var.RemoveValue(node_index)

        # Solve, displays a solution if any.
        assignment = routing.SolveWithParameters(search_parameters)
        if assignment:
            # Display solution.
            # Solution cost.
            print("Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n")
            time_dimension = routing.GetDimensionOrDie(time)

            for vehicle_nbr in range(num_vehicles):
                index = routing.Start(vehicle_nbr)
                index_next = assignment.Value(routing.NextVar(index))
                route = ''
                route_dist = 0

                while not routing.IsEnd(index_next):
                    node_index = routing.IndexToNode(index)
                    node_index_next = routing.IndexToNode(index_next)
                    time_var = time_dimension.CumulVar(index)
                    route += str(locations[node_index]) + str(assignment.Min(time_var)) + " to " + str(
                        assignment.Max(time_var)) + " -> "
                    # Add the distance to the next node.
                    route_dist += dist_callback(node_index, node_index_next)
                    index = index_next
                    index_next = assignment.Value(routing.NextVar(index))

                node_index = routing.IndexToNode(index)
                node_index_next = routing.IndexToNode(index_next)
                time_var = time_dimension.CumulVar(index)
                route += str(locations[node_index]) + str(assignment.Min(time_var)) + " to " + str(
                    assignment.Max(time_var))
                route_dist += dist_callback(node_index, node_index_next)
                print("Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n")
                print("Distance of route " + str(vehicle_nbr) + ": " + str(route_dist))
        else:
            print('No solution found.')
    else:
        print('Specify an instance greater than 0.')

def create_data_array():
    locations = [[9, 9], [11, 11], [10, 2], [10, 18], [2, 10], [18, 10], [2, 2], [18, 2], [2, 18], [18, 18],
                 [1000, 1000]]
    demands = [0 for _ in range(2)] + [1 for _ in range(8)] + [0]
    data = [locations, demands]
    return data


if __name__ == '__main__':
    main()

what is the problem?

[AlirezaTheH]

Hi Please answer my question in issuesit is very necessary for please!! On Wednesday, December 27, 2017 5:50 PM, Daniel J. H. <[email protected]> wrote: Number three is ticketed in #12.I don't have time to run this out - if you want to give it a try it mainly should be a matter of adding a new parameter and then passing it through to the solver (as described in the ticket).— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

[daniel-j-h]

@AlirezaH320 I currently don't have the time to look into this. Try to minimize your example and if you then can't get it to work ask around for pointers.

[emakarov]

@AlirezaH320 couple of comments.

1. Why do you think that your solution is not minimised by overall time? Your arccostevaluator indirectly is doing this.
2. I feel that this project is not completely relative to your code, because mapbox is creating a bridge for javascript, while your code is purely ortools-python. Maybe you can try to find an answer in google's ortools discussion group (in Google groups) or in google ortools issues on github.

[AlirezaTheH]

@emakarov couple of comments.

1. Because that gave me following result:

Total distance of all routes: 64

Route for vehicle 0:

[9, 9]0 to 0 -> [10, 2]8 to 8 -> [18, 2]21 to 21

Distance of route 0: 16
Route for vehicle 1:

[11, 11]0 to 0 -> [18, 10]8 to 8 -> [18, 18]21 to 21 -> [10, 18]34 to 34 -> [2, 18]47 to 47 -> [2, 10]60 to 60 -> [2, 2]73 to 73

Distance of route 1: 48

and as you see is not minimized
2. I tried to find any answer there but no one did reply

[emakarov]

you dont use any metaheuristic
thats why you have only first local minimum, and your solution is not optimized in general

[AlirezaTheH]

i used this:

search_parameters.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
        search_parameters.time_limit_ms = 30000

but it gave me same result can you give me an example @emakarov ?

[emakarov]

• 30 seconds can be too small
• you need to use kScalingFactor for integer programming

[Mizux]

What you want to use is SetGlobalSpanCoefficient to a distance/time dimension

I'm working on OR-Tools devsite/gh to add an example about this...
WorkInProgress: https://github.com/google/or-tools/tree/mizux/doc/doc#globalspan-on-distance-dimension

note1: this try to minimize max{cumul(end_i)}-min{cumul(start_i)} so while solver try to reduce the longest/biggest quantity, it won't perform a balancing (more a side effect sometime)
note2: you still need SetArcCost... for the first search so solver can find local minimum sometime playing with the vehicle capacity could change the result
e.g. https://github.com/google/or-tools/blob/mizux/doc/doc/vrpgs.py#L129 try to replace 3000 by 4000 ;)

ps: thanks for the js binding, hope to provide it directly in or-tools but low priority, no time currently....

[hopewise]

@AlirezaH320 as you are using start_locations I have an issue in the nodes order at the solution I get as here: google/or-tools#717 but I did not add any time concertinas yet..

Did you try to see if you change the start locations order in the locations list at create_data_array would results into different solution? (which I think should not happen)