Incremental Solving with an Initial Solution

When the Cloud Fleet Routing service solves a vehicle routing problem (VRP), it first generates an initial solution as a starting point for its search. If you already have a solution from a previous search, you can try to improve it by passing it to the Cloud Fleet Routing service as the initial solution for a new search. In many cases, this returns a solution with a lower total cost than the first one.

The solution you pass to the Cloud Fleet Routing service is called an injected solution.

Examples

This section includes a pair of examples to illustrate the injected solutions concept. Both examples solve the same capacitated VRP (in which the vehicles have a maximum capacity). The first example returns a solution without using an injected solution. The second example passes the first solution as an injected solution. These examples demonstrate how to use injected solutions, but the results are the same because the problem is simple. For complex problems, using injected solutions can get better results.

Call optimizeTours with no injected solution

Here is the full request example to call optimizeTours with no injected solution.

Python

To authenticate to Cloud Optimization, set up Application Default Credentials. For more information, see Set up authentication for a local development environment. 


from google.cloud import optimization_v1

# TODO(developer): Uncomment these variables before running the sample.
# project_id= 'YOUR_PROJECT_ID'


def call_sync_api(project_id: str) -> None:
    """Call the sync api for fleet routing."""
    # Use the default credentials for the environment.
    # Change the file name to your request file.
    request_file_name = "resources/sync_request.json"
    fleet_routing_client = optimization_v1.FleetRoutingClient()

    with open(request_file_name) as f:
        # The request must include the `parent` field with the value set to
        # 'projects/{YOUR_GCP_PROJECT_ID}'.
        fleet_routing_request = optimization_v1.OptimizeToursRequest.from_json(f.read())
        fleet_routing_request.parent = f"projects/{project_id}"
        # Send the request and print the response.
        # Fleet Routing will return a response by the earliest of the `timeout`
        # field in the request payload and the gRPC timeout specified below.
        fleet_routing_response = fleet_routing_client.optimize_tours(
            fleet_routing_request, timeout=100
        )
        print(fleet_routing_response)
        # If you want to format the response to JSON, you can do the following:
        # from google.protobuf.json_format import MessageToJson
        # json_obj = MessageToJson(fleet_routing_response._pb)

Response

When you send the request, it returns the following response in a JSON format.

{
   "routes":[
      {
         "travelSteps":[
            {
               "distanceMeters":4245.000000,
               "duration":"972s"
            },
            {
               "distanceMeters":2478.000000,
               "duration":"524s"
            },
            {
               "distanceMeters":3117.000000,
               "duration":"812s"
            }
         ],
         "vehicleDetour":"3034s",
         "vehicleEndTime":"1970-01-01T01:07:42Z",
         "vehicleStartTime":"1970-01-01T00:17:08Z",
         "visits":[
            {
               "detour":"0s",
               "isPickup":true,
               "startTime":"1970-01-01T00:33:20Z"
            },
            {
               "detour":"326s",
               "startTime":"1970-01-01T00:50:00Z"
            }
         ]
      },
      {
         "travelSteps":[
            {
               "distanceMeters":2557.000000,
               "duration":"620s"
            },
            {
               "distanceMeters":3433.000000,
               "duration":"789s"
            },
            {
               "distanceMeters":3800.000000,
               "duration":"1058s"
            }
         ],
         "vehicleDetour":"2929s",
         "vehicleEndTime":"1970-01-01T01:11:50Z",
         "vehicleIndex":1,
         "vehicleStartTime":"1970-01-01T00:23:01Z",
         "visits":[
            {
               "detour":"0s",
               "isPickup":true,
               "shipmentIndex":1,
               "startTime":"1970-01-01T00:33:21Z"
            },
            {
               "detour":"60s",
               "shipmentIndex":1,
               "startTime":"1970-01-01T00:50:01Z"
            }
         ]
      }
   ],
   "totalCost":5963.000000
}

The total cost of travel for this solution is 5963.

Example that uses an injected solution

In this example, we'll show how to include the solution shown previously as an injected solution in a new request to the Cloud Fleet Routing service. The JSON file for the request has three parts:

  • model: The core part of the request. This is the same model as the model in the first example.
  • injected_first_solution: Contains the response to the previous request.
  • The single line "extra_search_time_limit_ratio": "infinity":, an optional message that allows the solver to use all of its allowed computation time for the search. Without this line, the solver will stop after finding the first good solution.

The following shows where the three parts appear in the request.

{
  "model":{
    "globalStartTime":"1970-01-01T00:00:00+00:00",
    "globalEndTime":"1970-01-21T18:00:00+00:00",
    "shipments":[
      ...
  },
  "injectedFirstSolutionRoutes":[
    ...
  ]
  "searchMode": "CONSUME_ALL_AVAILABLE_TIME"
}

Call optimizeTours with injected solution

Here is the full request example to call optimizeTours with an injected solution.

Python

To authenticate to Cloud Optimization, set up Application Default Credentials. For more information, see Set up authentication for a local development environment. 


from google.cloud import optimization_v1

# TODO(developer): Uncomment these variables before running the sample.
# project_id= 'YOUR_PROJECT_ID'


def call_sync_api(project_id: str) -> None:
    """Call the sync api for fleet routing."""
    # Use the default credentials for the environment.
    # Change the file name to your request file.
    request_file_name = "resources/sync_request.json"
    fleet_routing_client = optimization_v1.FleetRoutingClient()

    with open(request_file_name) as f:
        # The request must include the `parent` field with the value set to
        # 'projects/{YOUR_GCP_PROJECT_ID}'.
        fleet_routing_request = optimization_v1.OptimizeToursRequest.from_json(f.read())
        fleet_routing_request.parent = f"projects/{project_id}"
        # Send the request and print the response.
        # Fleet Routing will return a response by the earliest of the `timeout`
        # field in the request payload and the gRPC timeout specified below.
        fleet_routing_response = fleet_routing_client.optimize_tours(
            fleet_routing_request, timeout=100
        )
        print(fleet_routing_response)
        # If you want to format the response to JSON, you can do the following:
        # from google.protobuf.json_format import MessageToJson
        # json_obj = MessageToJson(fleet_routing_response._pb)

Response

Here's the response.

{
   "routes":[
      {
         "travelSteps":[
            {
               "distanceMeters":4245.000000,
               "duration":"972s"
            },
            {
               "distanceMeters":2478.000000,
               "duration":"524s"
            },
            {
               "distanceMeters":3117.000000,
               "duration":"812s"
            }
         ],
         "vehicleDetour":"3034s",
         "vehicleEndTime":"1970-01-01T01:07:42Z",
         "vehicleStartTime":"1970-01-01T00:17:08Z",
         "visits":[
            {
               "detour":"0s",
               "isPickup":true,
               "startTime":"1970-01-01T00:33:20Z"
            },
            {
               "detour":"326s",
               "startTime":"1970-01-01T00:50:00Z"
            }
         ]
      },
      {
         "travelSteps":[
            {
               "distanceMeters":2557.000000,
               "duration":"620s"
            },
            {
               "distanceMeters":3433.000000,
               "duration":"789s"
            },
            {
               "distanceMeters":3800.000000,
               "duration":"1058s"
            }
         ],
         "vehicleDetour":"2929s",
         "vehicleEndTime":"1970-01-01T01:11:50Z",
         "vehicleIndex":1,
         "vehicleStartTime":"1970-01-01T00:23:01Z",
         "visits":[
            {
               "detour":"0s",
               "isPickup":true,
               "shipmentIndex":1,
               "startTime":"1970-01-01T00:33:21Z"
            },
            {
               "detour":"60s",
               "shipmentIndex":1,
               "startTime":"1970-01-01T00:50:01Z"
            }
         ]
      }
   ],
   "totalCost":5963.000000
}

When the problem is more complex, the total cost of travel would likely be improved over the solution in the first example because the second request would continue the optimization done in the first example.