python - 在Or工具中设置车辆路径问题的距离尺寸

Question

我正在尝试解决 5 名送货司机的车辆路线问题。我使用半正矢和经纬度来计算距离矩阵。我是 OR 工具的新手，所以以下是 vrp 示例。

问题在于，在 0f 5 个驾驶员中，仅为 2 个驾驶员生成了路线，并且这些路线非常长。我想生成多条较短的路线，以便利用所有司机。请检查我是否设置了错误的约束。

有人可以解释一下如何在 google OR-tools 中设置“距离”维度和 SetGlobalSpanCostCoefficient 吗？这是代码和输出。

from __future__ import print_function
import pandas as pd
import numpy as np
import googlemaps
import math
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

gmaps = googlemaps.Client(key='API Key')


def calculate_geocodes():
    df = pd.read_csv("banglore_zone.csv")

    df['lat'] = pd.Series(np.repeat(0, df.size), dtype=float)
    df['long'] = pd.Series(np.repeat(0, df.size), dtype=float)

    result = np.zeros([df.size, 2])
    for index, row in df.iterrows():
        # print(row['Address'])
        geocode_result = gmaps.geocode(row['Address'])[0]
        lat = (geocode_result['geometry']['location']['lat'])
        lng = (geocode_result['geometry']['location']['lng'])
        result[index] = lat, lng
        df.lat[index] = lat
        df.long[index] = lng

    print("First step", df)
    coords = df.as_matrix(columns=['lat', 'long'])

    return coords, df


def calculate_distance_matrix(coordinates, gmaps):
    distance_matrix = np.zeros(
        (np.size(coordinates, 0), np.size(coordinates, 0)))  # create an empty matrix for distance between all locations

    for index in range(0, np.size(coordinates, 0)):
        src = coordinates[index]

        for ind in range(0, np.size(coordinates, 0)):
            dst = coordinates[ind]
            distance_matrix[index, ind] = distance(src[0], src[1], dst[0], dst[1])

    return distance_matrix


def distance(lat1, long1, lat2, long2):
    # Note: The formula used in this function is not exact, as it assumes
    # the Earth is a perfect sphere.

    # Mean radius of Earth in miles
    radius_earth = 3959

    # Convert latitude and longitude to
    # spherical coordinates in radians.
    degrees_to_radians = math.pi / 180.0
    phi1 = lat1 * degrees_to_radians
    phi2 = lat2 * degrees_to_radians
    lambda1 = long1 * degrees_to_radians
    lambda2 = long2 * degrees_to_radians
    dphi = phi2 - phi1
    dlambda = lambda2 - lambda1

    a = haversine(dphi) + math.cos(phi1) * math.cos(phi2) * haversine(dlambda)
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
    d = radius_earth * c
    return d


def haversine(angle):
    h = math.sin(angle / 2) ** 2
    return h


def create_data_model(distance_matrix, number_of_vehicles, depot):
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = distance_matrix
    print(distance_matrix)

    data['num_vehicles'] = number_of_vehicles
    data['depot'] = depot
    return data


def print_solution(data, manager, routing, solution, address_dataframe):
    """Prints solution on console."""
    max_route_distance = 0

    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} ---> '.format(address_dataframe.iloc[manager.IndexToNode(index), 0])
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {}m'.format(max_route_distance))


def main():
    coordinates, address_dataframe = calculate_geocodes()
    distance_matrix = calculate_distance_matrix(coordinates, gmaps)
    data = create_data_model(distance_matrix, 5, 0)

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data['distance_matrix']), data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        80,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.seconds = 120
    search_parameters.log_search = False

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution, address_dataframe)


if __name__ == '__main__':
    main()

距离矩阵和输出是 -

>     [[ 0.          0.31543319  3.36774402 ...  8.79765925  8.94261055
>    8.83759758]  [ 0.31543319  0.          3.09418962 ...  8.81074289  8.95034082
>    8.84901702]  [ 3.36774402  3.09418962  0.         ... 10.87348059 10.97329493
>   10.89962072]  ...  [ 8.79765925  8.81074289 10.87348059 ...  0.          0.20726879
>    0.06082994]  [ 8.94261055  8.95034082 10.97329493 ...  0.20726879  0.
>    0.1465572 ]  [ 8.83759758  8.84901702 10.89962072 ...  0.06082994  0.1465572
>    0.        ]] Route for vehicle 0:  3Embed software 10th Cross St, RBI Colony, Ganganagar, Bengaluru, Karnataka 560024 ---> 0 Distance of
> the route: 0m
> 
> Route for vehicle 1:  3Embed software 10th Cross St, RBI Colony,
> Ganganagar, Bengaluru, Karnataka 560024 ---> 0 Distance of the route:
> 0m
> 
> Route for vehicle 2:  3Embed software 10th Cross St, RBI Colony,
> Ganganagar, Bengaluru, Karnataka 560024 --->  Sindhi High School,
> Kempapura --->  Hoppers stop Building No.12, Krishnaja Avenue, Near
> Kogilu Cross, International Airport Road, Yelahanka, Bengaluru ---> 
> Kempegowda International Airport Bengaluru --->  mvit International
> Airport Road, Hunasamaranahalli, Yelahanka, Krishnadeveraya Nagar,
> Bengaluru --->  Canadian International School 4 & 20, Manchenahalli,
> Yelahanka, Bengaluru --->  brick factory RMZ Galleria, Office Block,
> Ground Floor, B.B. Road, Yelahanka --->  Jakkur Aerodrome Bellary
> Road, Post, Yelahanka, Bengaluru, Karnataka --->  Godrej Platinum
> International Airport Road, Hebbal, Bengaluru, Karnataka --->  Vidya
> Niketan School 30, Kempapura Main Road, Kempapura, Hebbal, Bengaluru,
> Karnataka --->  Atria Institute of Technology, 1st Main Rd, Ags
> Colony, Anandnagar, Hebbal, Bengaluru, Karnataka ---> 0 Distance of
> the route: 26m
> 
> Route for vehicle 3:  3Embed software 10th Cross St, RBI Colony,
> Ganganagar, Bengaluru, Karnataka 560024 --->  Caffe cofee day CBI road
> banglore ---> 0 Distance of the route: 0m
> 
> Route for vehicle 4:  3Embed software 10th Cross St, RBI Colony,
> Ganganagar, Bengaluru, Karnataka 560024 --->  RT Nagar Police station
> --->  bus stop mekhri circle banglore --->  Truffles  80 Feet Road, Jaladarsini Layout, Sanjaynagar Banglore --->  BEL circle banglore
> --->  Paragon Outlet Shivapura, Peenya, Bengaluru --->  Taj vivanta Yeshwantpur, Bengaluru --->  Orion Mall A Block, Brigade Gateway, Dr
> Rajkumar Rd, Malleshwaram, Bengaluru --->  brand factory Malleshwaram
> Banglore  --->  Mantri Square Mall, Sampige Road, Malleshwaram,
> Bengaluru, Karnataka --->  Krantivira Sangolli Rayanna Bengaluru, M.G.
> Railway Colony, Majestic, Bengaluru --->  UB city banglore ---> 
> Brigade road banglore --->  MG Road metro station Banglore ---> 
> commercial street bangalore --->  Infantry Road, Beside Prestige
> Building, Tasker Town, Shivaji Nagar, Bengaluru, Karnataka ---> 
> Garuda Mall Magrath Rd, Ashok Nagar, Bengaluru --->  Brand Factory -
> Home Town Above HomeTown, Vanshee Towers, Survey No.92/4 3rd and 4th
> Floors, Outer Ring Rd, Marathahalli, Bengaluru --->  KLM Shopping
> Mall, Marathahalli Bridge Marathahalli  --->  Favourite Shop HAL Old
> Airport Rd, Subbaiah Reddy Colony, Marathahalli Village, Marathahalli,
> Bengaluru --->  Max RPR Plaza, Varthur Rd, Marathahalli, Bengaluru
> --->  Pick 'n' Move Shop No. 102, Ground Floor, Varthur Rd, Marathahalli Village, Marathahalli, Bengaluru --->  Lotto Shoes 45/2,
> Varthur Rd, Marathahalli Village, Marathahalli, Bengaluru, Karnataka 
> --->  The Raymond Shop Opp. Mga Hospital, Marathalli Main Road Near Ring Road Junction, Bengaluru, Karnataka --->  chinnaswamy stadium
> banglore --->  fun cinemas cunningham road Banglore --->  Cant station
> banglore --->  Radhakrishna Theatre 25, 1st Main Rd, Mattdahally, RT
> Nagar, Bengaluru --->  Presidency School Near R T Nagar, HMT Layout,
> Bengaluru, Karnataka ---> 0 Distance of the route: 20m
> 
> Maximum of the route distances: 26m

Answer 1

您应该减少车辆最大行驶距离。目前您将其设置为 80。您的路线距离为 20 和 26。

routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        80,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)