OR-tools VRP 求解器为每辆车返回一项作业

Question

我正在 python 中使用 Google OR-Tools 来解决带取货/送货功能的 VRP 问题。在许多情况下，求解器运行良好并返回合理的解决方案，但我们发现，对于某些数据集，求解器始终会为每辆卡车返回一个作业，无论路线所涉及的时间如何。

我的模型设置如下：

我的初始车辆数量等于数据集中的工作数量，并且我们允许 OR-Tools 自动最小化卡车数量。

每个作业的取货地点的需求为 1，每个作业的投递地点的需求为 -1，以便在取货后立即强制投递。

我们将每辆车的最长行驶时间设置为 8 小时。

然后，每个作业都有一个相关的提货数量，我们根据卡车的容量将该作业分成多个交付。例如，如果一项工作需要交付 60 吨，我们将其表示为三个工作，每个工作 20 吨（美国州际公路上允许车辆运载的最大数量）。

现在，我们有一个简单的数据集，取货地点为：698 Longtown Rd, Columbia, SC，下车地点为：121 Chappell Creek Rd Hopkins, SC。车程为 32 分钟，总行程时间为 64 分钟。这项工作的相关数量为 60 吨，需要 3 辆卡车装载。

我们从 or-tools 收到的结果显示每辆卡车装载一次，并且无论我们允许求解器运行多长时间，该结果都不会改变。最佳解决方案是让一辆卡车完成所有负载，因为这仍然大大低于 8 小时的驾驶时间限制。

这是我的代码：

import json
import math
import traceback
import urllib
import redis
import requests

import boto3
from signal import signal, SIGINT, SIGTERM

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

url = 'https://test-api.truckit.com/api/2/signin'
api_data = {"password": "", "username": ""}
response = requests.post(url, json=api_data)
api_data = response.json()


def build_auth_header(token):
    header = {'Authorization': f'Token {token}'}
    return header


class SignalHandler:
    def __init__(self):
        self.received_signal = False
        signal(SIGINT, self._signal_handler)
        signal(SIGTERM, self._signal_handler)

    def _signal_handler(self, signal, frame):
        print(f"handling signal {signal}, exiting gracefully")
        self.received_signal = True


sqs = boto3.resource("sqs")
queue = sqs.get_queue_by_name(QueueName="")
redisClient = redis.Redis(host='', port=6379,
                          password='')


def create_distance_matrix(data):
    addresses = data["addresses"]

    API_key = data["API_key"]
    origin_addresses = []
    dest_addresses = addresses
    distance_matrix = []
    responses = {}
    responses['destination_addresses'] = []
    responses['origin_addresses'] = []
    responses['rows'] = []

    # Send q requests, returning max_rows rows per request.
    for i in range(0, len(addresses)):
        origin_addresses.clear()
        origin_addresses.append(addresses[i])

        for j in range(0, len(addresses), 25):

            dest_addresses_request = addresses[j:j + 25]

            response = send_request(origin_addresses, dest_addresses_request, API_key)
            responses['origin_addresses'] = response['origin_addresses']
            for destination_address in response['destination_addresses']:
                responses['destination_addresses'].append(destination_address)
            for row in response['rows']:
                if len(responses['rows']) == 0:
                    responses['rows'].append(row)
                else:
                    for element in row['elements']:
                        responses['rows'][0]['elements'].append(element)

        distance_matrix += build_distance_matrix(responses)
        responses['origin_addresses'].clear()
        responses['destination_addresses'].clear()
        responses['rows'].clear()

    return distance_matrix


def send_request(origin_addresses, dest_addresses, API_key):
    """ Build and send request for the given origin and destination addresses."""

    def build_address_str(addresses):
        # Build a pipe-separated string of addresses
        address_str = ''
        for i in range(len(addresses) - 1):
            address_str += addresses[i] + '|'
        address_str += addresses[-1]
        return address_str

    request = 'https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial'
    origin_address_str = build_address_str(origin_addresses)

    dest_address_str = build_address_str(dest_addresses)
    request = request + '&origins=' + origin_address_str + '&destinations=' + \
              dest_address_str + '&key=' + API_key

    jsonResult = urllib.request.urlopen(request).read()
    response = json.loads(jsonResult)

    return response


def build_distance_matrix(response):
    distance_matrix = []
    for row in response['rows']:
        row_list = [row['elements'][j]['duration']['value'] for j in range(len(row['elements']))]
        distance_matrix.append(row_list)

    return distance_matrix


def process_message(message_body):
    print(f"processing message: {message_body}")
    data = json.loads(message_body)
    data_matrix = {}
    data_matrix['problem_id'] = data['problemId']
   
    data_matrix["addresses"] = []
    data_matrix["pickups_deliveries"] = []
    data_matrix["demands"] = []
    data_matrix["jobOrderIDs"] = []
    depot_address = str(data["depot"]["latitude"]) + "," + str(data["depot"]["longitude"])
    data_matrix["jobOrderIDs"].append(0)
    data_matrix["addresses"].append(depot_address)
    hash_key = data["hashKey"]

    for location in data["locationList"]:

        pick_lat = location["PickupLatitude"]
        pick_long = location["PickupLongitude"]

        drop_lat = location["DropoffLatitude"]
        drop_long = location["DropoffLongitude"]

        jobOrderId = location["jobOrderID"]

        demand = math.ceil(float(int(location["totalQuantity"]) / 20))


        for i in range(0, demand):
            data_matrix["addresses"].append(str(pick_lat) + ',' + str(pick_long))
            data_matrix["addresses"].append(str(drop_lat) + ',' + str(drop_long))
            data_matrix["jobOrderIDs"].append(str(jobOrderId))
            data_matrix["jobOrderIDs"].append(str(jobOrderId))

    data_matrix["demands"].append(0)
    for i in range(1, len(data_matrix["addresses"]) - 1, 2):
        data_matrix["pickups_deliveries"].append([i, i + 1])
        data_matrix["demands"].append(1)
        data_matrix["demands"].append(-1)

    data_matrix["num_vehicles"] = int(len(data_matrix["addresses"]) / 2)
    data_matrix["vehicle_capacities"] = []

    for i in range(0, data_matrix["num_vehicles"]):
        data_matrix["vehicle_capacities"].append(1)

    data_matrix["depot"] = 0
    data_matrix["API_key"] = ''

    data_matrix["distance_matrix"] = create_distance_matrix(data_matrix)

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

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

    # Define cost of each arc.
    def distance_callback(from_index, to_index):
        """Returns the manhattan 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_matrix['distance_matrix'][from_node][to_node]*1000

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

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

    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data_matrix['demands'][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(
        demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data_matrix['vehicle_capacities'],  # vehicle maximum capacities
        True,  # start cumul to zero
        'Capacity')


    # Define Transportation Requests.
    for request in data_matrix['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) == routing.VehicleVar(
                delivery_index))
        routing.solver().Add(
            distance_dimension.CumulVar(pickup_index) <=
            distance_dimension.CumulVar(delivery_index))
    
    # 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 = 1200
    search_parameters.log_search = True
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)
    search_parameters.use_full_propagation = True
    # Solve the problem.

    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        solution_dict = {}

        for vehicle_id in range(data_matrix['num_vehicles']):

            index = routing.Start(vehicle_id)
            plan_output = ''
            route_distance = 0
            route_load = 0
            while not routing.IsEnd(index):
                node_index = manager.IndexToNode(index)

                plan_output += '{0},'.format(data_matrix['jobOrderIDs'][node_index])
                previous_index = index
                index = solution.Value(routing.NextVar(index))

            plan_output += '{0},'.format(data_matrix['jobOrderIDs'][manager.IndexToNode(index)])

            plan_output = plan_output[:-1]
            plan_words = plan_output.split(",")
            plan_output = ''
            for i in range(len(plan_words)):
                if (i % 2 == 0):
                    plan_output += plan_words[i] + ","
            plan_output = plan_output[:-1]
            plan_output += ",0"
            if plan_output != 0 and plan_output != str(0) and plan_output != str('0,0'):
                print(plan_output)
                solution_dict[vehicle_id] = plan_output

        # trucks_url = 'https://test-api.truckit.com/api/2/trucks'
        trucks_url = 'https://test-api.truckit.com/api/2/job-orders/smart-dispatch/' + str(data_matrix['problem_id'])
        head = build_auth_header(api_data["authToken"])
        status = {}
        ride_list = []
        dummy_location_dict = {}
        dummy_id_dict = {}
        dummy_id_dict["id"] = 0
        dummy_id_dict["name"] = ""
        dummy_location_dict["location"] = dummy_id_dict
        dummy_location_dict["timestamp"] = 0

        ride_list.append(dummy_location_dict)

        redisClient.hset(hash_key, "solution", json.dumps(solution_dict))
        redisClient.hset(hash_key, "ride_list", json.dumps(ride_list))
        json_data = {"status": "completed"}

        api_response = requests.post(trucks_url, headers=head, json=json_data)

        print_solution(data_matrix, manager, routing, solution)


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    total_distance = 0
    total_load = 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
        route_load = 0
        while not routing.IsEnd(index):

            node_index = manager.IndexToNode(index)

            plan_output += ' {0} -> '.format(node_index)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            try:
                distance = data['distance_matrix'][previous_index][index]
                route_distance += distance
            except:
                distance = distance

        plan_output += ' {0}\n'.format(manager.IndexToNode(index))
        plan_output += 'Time of the route: {} hours\n'.format(str(float(route_distance / (60 * 60))))
        print(plan_output)
        total_distance += route_distance

    print('Total distance of all routes: {}m'.format(total_distance))


if __name__ == "__main__":
    signal_handler = SignalHandler()
    while not signal_handler.received_signal:
        messages = queue.receive_messages(
            MaxNumberOfMessages=1,
            WaitTimeSeconds=1
        )
        for message in messages:
            try:
                process_message(message.body)

                message.delete()

            except Exception as e:
                print(f"exception while processing message: {repr(e)}")
                traceback.print_exc()
                continue

            message.delete()

如果有人对问题可能是什么有任何建议，我们非常感谢您的帮助。