Bu bölümde, kısıtlamalar nedeniyle uygulanabilir bir çözümü olmayan yönlendirme sorunlarının nasıl ele alınacağı açıklanmaktadır. Örneğin, tüm konumlardaki toplam talebin araçların toplam kapasitesini aştığı kapasite kısıtlamaları olan bir TTP verildiyse bir çözüm mümkün olmaz. Bu gibi durumlarda araçlar, ziyaretleri belirli konumlara bırakmalıdır. Sorun, hangi ziyaretlerin düşeceğine karar vermektir.
Sorunu çözmek için tüm konumlarda ceza adı verilen yeni bir maliyet sunuyoruz. Bir konuma yapılan ziyaret düştüğünde ceza, katedilen toplam mesafeye eklenir. Çözümleyici, daha sonra toplam mesafeyi en aza indiren bir rotanın yanı sıra tüm bırakılan konumlara ait cezaların toplamını gösterir.
Örneğin, aşağıdaki grafikte belirtilen kapasite kısıtlamalarına sahip basit üçlü VRP'yi düşünün. Burada, üç konumun yanındaki sayıların (depo dışında) talep görmesi gerekir.
Kapasitesi 50 olan yalnızca bir araç olduğunu varsayalım. Toplam talep 60 olduğu için A, B ve C konumlarının üçünü de ziyaret edemez. Sorunu çözmek için her konuma 100 gibi büyük bir ceza atarsınız. Sorunun çözülmüş olduğunu tespit eden problem çözücü, B konumunu bırakıp şu rotayı döndürür: Depot -> A -> C -> Depot
Bu, üç konumdan ikisini (mesafe 55) ziyaret eden en kısa rotadır.
Ceza boyutları
Yukarıdaki örnekte, konumlar arasındaki tüm mesafelerin toplamından (depo hariç) daha büyük cezalar seçtik. Sonuç olarak, problemi uygulanabilir hale getirmek için bir konumdan ayrıldıktan sonra problem çözücünün cezası seyahat mesafesindeki diğer azalmaları aşacağından, problem çözme aracı hiçbir ek konumu bırakmaz.
Mümkün olduğunca çok teslimat yapmak istediğinizi varsayarsak bu soruna tatmin edici bir çözüm sağlar.
Mümkün olduğunca çok sayıda teslimat yapmanız gerekmiyorsa daha küçük cezalar verebilirsiniz. Bu durumda, problemi çözücü, sorunu makul hale getirmek için gerekenden daha fazla konum bırakabilir. Örneğin, belirli yerleri ziyaret etmeye ek olarak temel seyahat maliyetinin üzerinde olan ek maliyetler varsa da bunu yapabilirsiniz.
Örnek
Şimdi, cezalarla çözülebilecek daha büyük bir VRP örneği sunuyoruz. Örnek, önceki CVRP örneğine benzerdir ancak bu kez bazı talepleri artırdık ve bazı araçları ziyaret etmeyi bırakmaya zorladık.
Konumların ve yeni taleplerin grafiği aşağıda verilmiştir.
Örneği VEYA Araçları ile çözme
Aşağıdaki bölümlerde örneğin OR-Tools ile nasıl çözümleneceği açıklanmaktadır.
Verileri oluşturma
Bu örnekteki veriler, önceki VRP örneğindeki verileri kapsar ve aşağıdaki talepleri ve kapasiteleri içerir:
Python
data["demands"] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8]
data["vehicle_capacities"] = [15, 15, 15, 15]
C++
const std::vector<int64_t> demands{
0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8,
};
const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15};
Java
public final long[] demands = {0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8};
public final long[] vehicleCapacities = {15, 15, 15, 15};
C#
public long[] Demands = { 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8 };
public long[] VehicleCapacities = { 15, 15, 15, 15 };
Kapasite kısıtlamaları ve cezalar ekleyin
Aşağıdaki kod, talep geri çağırma ve kapasite kısıtlamalarını ve AddDisjunction yöntemini kullanarak cezalar ekler.
Python
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["demands"][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data["vehicle_capacities"], # vehicle maximum capacities
True, # start cumul to zero
"Capacity",
)
# Allow to drop nodes.
penalty = 1000
for node in range(1, len(data["distance_matrix"])):
routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
C++
const int demand_callback_index = routing.RegisterUnaryTransitCallback(
[&data, &manager](const int64_t from_index) -> int64_t {
// Convert from routing variable Index to demand NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
return data.demands[from_node];
});
routing.AddDimensionWithVehicleCapacity(
demand_callback_index, // transit callback index
int64_t{0}, // null capacity slack
data.vehicle_capacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
// Allow to drop nodes.
int64_t penalty{1000};
for (int i = 1; i < data.distance_matrix.size(); ++i) {
routing.AddDisjunction(
{manager.NodeToIndex(RoutingIndexManager::NodeIndex(i))}, penalty);
}
Java
final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
return data.demands[fromNode];
});
routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.vehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
// Allow to drop nodes.
long penalty = 1000;
for (int i = 1; i < data.distanceMatrix.length; ++i) {
routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty);
}
C#
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
{
// Convert from routing variable Index to
// demand NodeIndex.
var fromNode =
manager.IndexToNode(fromIndex);
return data.Demands[fromNode];
});
routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.VehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
// Allow to drop nodes.
long penalty = 1000;
for (int i = 1; i < data.DistanceMatrix.GetLength(0); ++i)
{
routing.AddDisjunction(new long[] { manager.NodeToIndex(i) }, penalty);
}
Bu bağlamda bağımsızlık, problem çözücünün belirli bir konumu çözüme dahil edip etmemeye karar vermek için kullandığı bir değişkendir. Bu örnekte, yöntem her bir konuma aynı cezayı eklese de genel olarak farklı konumlara farklı cezalar ekleyebilirsiniz.
Çözüm yazıcısını ekleyin
Aşağıda gösterilen çözüm yazıcısı, CVRP örneğindeki yazıcıya benzer, ancak aynı zamanda bırakılan konumları da gösterir.
Python
def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
print(f"Objective: {assignment.ObjectiveValue()}")
# Display dropped nodes.
dropped_nodes = "Dropped nodes:"
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if assignment.Value(routing.NextVar(node)) == node:
dropped_nodes += f" {manager.IndexToNode(node)}"
print(dropped_nodes)
# Display routes
total_distance = 0
total_load = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data["demands"][node_index]
plan_output += f" {node_index} Load({route_load}) -> "
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
plan_output += f"Distance of the route: {route_distance}m\n"
plan_output += f"Load of the route: {route_load}\n"
print(plan_output)
total_distance += route_distance
total_load += route_load
print(f"Total Distance of all routes: {total_distance}m")
print(f"Total Load of all routes: {total_load}")
C++
//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
// Display dropped nodes.
std::ostringstream dropped_nodes;
for (int64_t node = 0; node < routing.Size(); ++node) {
if (routing.IsStart(node) || routing.IsEnd(node)) continue;
if (solution.Value(routing.NextVar(node)) == node) {
dropped_nodes << " " << manager.IndexToNode(node).value();
}
}
LOG(INFO) << "Dropped nodes:" << dropped_nodes.str();
// Display routes
int64_t total_distance{0};
int64_t total_load{0};
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64_t route_distance{0};
int64_t route_load{0};
std::ostringstream route;
while (!routing.IsEnd(index)) {
const int node_index = manager.IndexToNode(index).value();
route_load += data.demands[node_index];
route << node_index << " Load(" << route_load << ") -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64_t{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
LOG(INFO) << "Load of the route: " << route_load;
total_distance += route_distance;
total_load += route_load;
}
LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
LOG(INFO) << "Total load of all routes: " << total_load;
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
Java
/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
// Display dropped nodes.
String droppedNodes = "Dropped nodes:";
for (int node = 0; node < routing.size(); ++node) {
if (routing.isStart(node) || routing.isEnd(node)) {
continue;
}
if (solution.value(routing.nextVar(node)) == node) {
droppedNodes += " " + manager.indexToNode(node);
}
}
logger.info(droppedNodes);
// Display routes
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
long routeLoad = 0;
String route = "";
while (!routing.isEnd(index)) {
long nodeIndex = manager.indexToNode(index);
routeLoad += data.demands[(int) nodeIndex];
route += nodeIndex + " Load(" + routeLoad + ") -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
route += manager.indexToNode(routing.end(i));
logger.info(route);
logger.info("Distance of the route: " + routeDistance + "m");
totalDistance += routeDistance;
totalLoad += routeLoad;
}
logger.info("Total Distance of all routes: " + totalDistance + "m");
logger.info("Total Load of all routes: " + totalLoad);
}
C#
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager,
in Assignment solution)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// Inspect solution.
// Display dropped nodes.
string droppedNodes = "Dropped nodes:";
for (int index = 0; index < routing.Size(); ++index)
{
if (routing.IsStart(index) || routing.IsEnd(index))
{
continue;
}
if (solution.Value(routing.NextVar(index)) == index)
{
droppedNodes += " " + manager.IndexToNode(index);
}
}
Console.WriteLine("{0}", droppedNodes);
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
long routeLoad = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
long nodeIndex = manager.IndexToNode(index);
routeLoad += data.Demands[nodeIndex];
Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad);
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
totalDistance += routeDistance;
totalLoad += routeLoad;
}
Console.WriteLine("Total Distance of all routes: {0}m", totalDistance);
Console.WriteLine("Total Load of all routes: {0}m", totalLoad);
}
Programı çalıştırma
Bu program, çalıştırıldığında aşağıda gösterilen çıkışı döndürür. Çözücünün 6 ve 15 konumlarını bıraktığını unutmayın.
Objective: 7936 Dropped nodes: 6 15 Route for vehicle 0: 0 Load(0) -> 9 Load(1) -> 14 Load(7) -> 16 Load(15) -> 0 Load(15) Distance of the route: 1324m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 12 Load(2) -> 11 Load(3) -> 4 Load(9) -> 3 Load(12) -> 1 Load(13) -> 0 Load(13) Distance of the route: 1872m Load of the route: 13 Route for vehicle 2: 0 Load(0) -> 7 Load(8) -> 13 Load(14) -> 0 Load(14) Distance of the route: 868m Load of the route: 14 Route for vehicle 3: 0 Load(0) -> 8 Load(8) -> 10 Load(10) -> 2 Load(11) -> 5 Load(14) -> 0 Load(14) Distance of the route: 1872m Load of the route: 14 Total Distance of all routes: 5936m Total Load of all routes: 56
Rotaları aşağıda görebilirsiniz.
Tamamlanan programlar
Tam programları burada bulabilirsiniz.
Python
"""Capacited Vehicles Routing Problem (CVRP)."""
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["distance_matrix"] = [
# fmt: off
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
# fmt: on
]
data["demands"] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8]
data["vehicle_capacities"] = [15, 15, 15, 15]
data["num_vehicles"] = 4
data["depot"] = 0
return data
def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
print(f"Objective: {assignment.ObjectiveValue()}")
# Display dropped nodes.
dropped_nodes = "Dropped nodes:"
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if assignment.Value(routing.NextVar(node)) == node:
dropped_nodes += f" {manager.IndexToNode(node)}"
print(dropped_nodes)
# Display routes
total_distance = 0
total_load = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data["demands"][node_index]
plan_output += f" {node_index} Load({route_load}) -> "
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
plan_output += f"Distance of the route: {route_distance}m\n"
plan_output += f"Load of the route: {route_load}\n"
print(plan_output)
total_distance += route_distance
total_load += route_load
print(f"Total Distance of all routes: {total_distance}m")
print(f"Total Load of all routes: {total_load}")
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# 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 Capacity constraint.
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["demands"][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data["vehicle_capacities"], # vehicle maximum capacities
True, # start cumul to zero
"Capacity",
)
# Allow to drop nodes.
penalty = 1000
for node in range(1, len(data["distance_matrix"])):
routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
)
search_parameters.time_limit.FromSeconds(1)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if assignment:
print_solution(data, manager, routing, assignment)
if __name__ == "__main__":
main()
C++
#include <cstdint>
#include <sstream>
#include <vector>
#include "google/protobuf/duration.pb.h"
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"
namespace operations_research {
struct DataModel {
const std::vector<std::vector<int64_t>> distance_matrix{
{0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468,
776, 662},
{548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
1016, 868, 1210},
{776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130,
788, 1552, 754},
{696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
1164, 560, 1358},
{582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
1050, 674, 1244},
{274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514,
1050, 708},
{502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514,
1278, 480},
{194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662,
742, 856},
{308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320,
1084, 514},
{194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274,
810, 468},
{536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730,
388, 1152, 354},
{502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308,
650, 274, 844},
{388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536,
388, 730},
{354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342,
422, 536},
{468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342,
0, 764, 194},
{776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388,
422, 764, 0, 798},
{662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536,
194, 798, 0},
};
const std::vector<int64_t> demands{
0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8,
};
const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15};
const int num_vehicles = 4;
const RoutingIndexManager::NodeIndex depot{0};
};
//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
// Display dropped nodes.
std::ostringstream dropped_nodes;
for (int64_t node = 0; node < routing.Size(); ++node) {
if (routing.IsStart(node) || routing.IsEnd(node)) continue;
if (solution.Value(routing.NextVar(node)) == node) {
dropped_nodes << " " << manager.IndexToNode(node).value();
}
}
LOG(INFO) << "Dropped nodes:" << dropped_nodes.str();
// Display routes
int64_t total_distance{0};
int64_t total_load{0};
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64_t route_distance{0};
int64_t route_load{0};
std::ostringstream route;
while (!routing.IsEnd(index)) {
const int node_index = manager.IndexToNode(index).value();
route_load += data.demands[node_index];
route << node_index << " Load(" << route_load << ") -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64_t{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
LOG(INFO) << "Load of the route: " << route_load;
total_distance += route_distance;
total_load += route_load;
}
LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
LOG(INFO) << "Total load of all routes: " << total_load;
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
void VrpDropNodes() {
// Instantiate the data problem.
DataModel data;
// Create Routing Index Manager
RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
data.depot);
// Create Routing Model.
RoutingModel routing(manager);
// Create and register a transit callback.
const int transit_callback_index = routing.RegisterTransitCallback(
[&data, &manager](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int to_node = manager.IndexToNode(to_index).value();
return data.distance_matrix[from_node][to_node];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
// Add Capacity constraint.
const int demand_callback_index = routing.RegisterUnaryTransitCallback(
[&data, &manager](const int64_t from_index) -> int64_t {
// Convert from routing variable Index to demand NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
return data.demands[from_node];
});
routing.AddDimensionWithVehicleCapacity(
demand_callback_index, // transit callback index
int64_t{0}, // null capacity slack
data.vehicle_capacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
// Allow to drop nodes.
int64_t penalty{1000};
for (int i = 1; i < data.distance_matrix.size(); ++i) {
routing.AddDisjunction(
{manager.NodeToIndex(RoutingIndexManager::NodeIndex(i))}, penalty);
}
// Setting first solution heuristic.
RoutingSearchParameters search_parameters = DefaultRoutingSearchParameters();
search_parameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
search_parameters.set_local_search_metaheuristic(
LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH);
search_parameters.mutable_time_limit()->set_seconds(1);
// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(search_parameters);
// Print solution on console.
PrintSolution(data, manager, routing, *solution);
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::VrpDropNodes();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.LocalSearchMetaheuristic;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import com.google.protobuf.Duration;
import java.util.logging.Logger;
/** Minimal VRP.*/
public class VrpDropNodes {
private static final Logger logger = Logger.getLogger(VrpDropNodes.class.getName());
static class DataModel {
public final long[][] distanceMatrix = {
{0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
{548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
{776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
{696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
{582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
{274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
{502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
{194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
{308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
{194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
{536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
{502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
{388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
{354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
{468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
{776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
{662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0},
};
public final long[] demands = {0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8};
public final long[] vehicleCapacities = {15, 15, 15, 15};
public final int vehicleNumber = 4;
public final int depot = 0;
}
/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
// Display dropped nodes.
String droppedNodes = "Dropped nodes:";
for (int node = 0; node < routing.size(); ++node) {
if (routing.isStart(node) || routing.isEnd(node)) {
continue;
}
if (solution.value(routing.nextVar(node)) == node) {
droppedNodes += " " + manager.indexToNode(node);
}
}
logger.info(droppedNodes);
// Display routes
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
long routeLoad = 0;
String route = "";
while (!routing.isEnd(index)) {
long nodeIndex = manager.indexToNode(index);
routeLoad += data.demands[(int) nodeIndex];
route += nodeIndex + " Load(" + routeLoad + ") -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
route += manager.indexToNode(routing.end(i));
logger.info(route);
logger.info("Distance of the route: " + routeDistance + "m");
totalDistance += routeDistance;
totalLoad += routeLoad;
}
logger.info("Total Distance of all routes: " + totalDistance + "m");
logger.info("Total Load of all routes: " + totalLoad);
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate the data problem.
final DataModel data = new DataModel();
// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Create and register a transit callback.
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return data.distanceMatrix[fromNode][toNode];
});
// Define cost of each arc.
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Add Capacity constraint.
final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
return data.demands[fromNode];
});
routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.vehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
// Allow to drop nodes.
long penalty = 1000;
for (int i = 1; i < data.distanceMatrix.length; ++i) {
routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty);
}
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
.setTimeLimit(Duration.newBuilder().setSeconds(1).build())
.build();
// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);
// Print solution on console.
printSolution(data, routing, manager, solution);
}
}
C#
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
using Google.Protobuf.WellKnownTypes; // Duration
/// <summary>
/// Minimal Vrp with drop nodes.
/// </summary>
public class VrpDropNodes
{
class DataModel
{
public long[,] DistanceMatrix = {
{ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 },
{ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 },
{ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 },
{ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 },
{ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 },
{ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 },
{ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 },
{ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 },
{ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 },
{ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 },
{ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 },
{ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 },
{ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 },
{ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 },
{ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 },
{ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 },
{ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 }
};
public long[] Demands = { 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8 };
public long[] VehicleCapacities = { 15, 15, 15, 15 };
public int VehicleNumber = 4;
public int Depot = 0;
};
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager,
in Assignment solution)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// Inspect solution.
// Display dropped nodes.
string droppedNodes = "Dropped nodes:";
for (int index = 0; index < routing.Size(); ++index)
{
if (routing.IsStart(index) || routing.IsEnd(index))
{
continue;
}
if (solution.Value(routing.NextVar(index)) == index)
{
droppedNodes += " " + manager.IndexToNode(index);
}
}
Console.WriteLine("{0}", droppedNodes);
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
long routeLoad = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
long nodeIndex = manager.IndexToNode(index);
routeLoad += data.Demands[nodeIndex];
Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad);
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
totalDistance += routeDistance;
totalLoad += routeLoad;
}
Console.WriteLine("Total Distance of all routes: {0}m", totalDistance);
Console.WriteLine("Total Load of all routes: {0}m", totalLoad);
}
public static void Main(String[] args)
{
// Instantiate the data problem.
DataModel data = new DataModel();
// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Create and register a transit callback.
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to
// distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.DistanceMatrix[fromNode, toNode];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Add Capacity constraint.
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
{
// Convert from routing variable Index to
// demand NodeIndex.
var fromNode =
manager.IndexToNode(fromIndex);
return data.Demands[fromNode];
});
routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.VehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
// Allow to drop nodes.
long penalty = 1000;
for (int i = 1; i < data.DistanceMatrix.GetLength(0); ++i)
{
routing.AddDisjunction(new long[] { manager.NodeToIndex(i) }, penalty);
}
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
searchParameters.TimeLimit = new Duration { Seconds = 1 };
// Solve the problem.
Assignment solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
PrintSolution(data, routing, manager, solution);
}
}