ক্যাপাসিটেটেড ভেহিকল রাউটিং সমস্যা (CVRP) হল একটি VRP যেখানে সীমিত বহন ক্ষমতা সহ যানবাহনগুলিকে বিভিন্ন স্থানে আইটেম তুলতে বা বিতরণ করতে হয়। আইটেমগুলির একটি পরিমাণ রয়েছে, যেমন ওজন বা ভলিউম, এবং যানবাহনগুলির সর্বাধিক ক্ষমতা রয়েছে যা তারা বহন করতে পারে। সমস্যাটি হল সর্বনিম্ন খরচে আইটেমগুলি তোলা বা বিতরণ করা, যখন যানবাহনের ধারণক্ষমতা কখনই ছাড়িয়ে যায় না।
নিম্নলিখিত উদাহরণে, আমরা অনুমান করি যে সমস্ত আইটেম তোলা হচ্ছে। এই সমস্যার সমাধানকারী প্রোগ্রামটিও কাজ করে যদি সমস্ত আইটেম সরবরাহ করা হয়: এই ক্ষেত্রে, আপনি ভাবতে পারেন যে যখন যানবাহনগুলি ডিপো থেকে সম্পূর্ণ লোড করে চলে যায় তখন ক্ষমতার সীমাবদ্ধতা প্রয়োগ করা হয়। কিন্তু ক্ষমতার সীমাবদ্ধতা উভয় ক্ষেত্রেই একইভাবে প্রয়োগ করা হয়।
CVRP উদাহরণ
এর পরে, আমরা ক্ষমতার সীমাবদ্ধতা সহ একটি VRP-এর উদাহরণ বর্ণনা করি। উদাহরণটি পূর্ববর্তী VRP উদাহরণকে প্রসারিত করে এবং নিম্নলিখিত প্রয়োজনীয়তাগুলি যোগ করে৷ প্রতিটি অবস্থানে আইটেম বাছাই করা পরিমাণের সাথে সামঞ্জস্যপূর্ণ একটি চাহিদা আছে। এছাড়াও, প্রতিটি গাড়ির সর্বোচ্চ ক্ষমতা 15। (আমরা চাহিদা বা ক্ষমতার জন্য ইউনিট নির্দিষ্ট করছি না।)
নীচের গ্রিড নীল রঙে এবং কোম্পানির অবস্থান কালো রঙে দেখার জন্য অবস্থানগুলি দেখায়৷ চাহিদা প্রতিটি অবস্থানের নীচের ডানদিকে দেখানো হয়. অবস্থানগুলি কীভাবে সংজ্ঞায়িত করা হয় সে সম্পর্কে আরও বিশদ বিবরণের জন্য VRP বিভাগে অবস্থান স্থানাঙ্ক দেখুন৷
সমস্যা হল যানবাহনগুলির রুটগুলির একটি অ্যাসাইনমেন্ট খুঁজে বের করা যা সর্বনিম্ন মোট দূরত্ব রয়েছে এবং এমন যে মোট পরিমাণ একটি যানবাহন বহন করছে তা কখনই তার ধারণক্ষমতা অতিক্রম করে না।
OR-Tools দিয়ে CVRP উদাহরণ সমাধান করা
নিম্নলিখিত বিভাগগুলি ব্যাখ্যা করে কিভাবে OR-Tools দিয়ে CVRP উদাহরণ সমাধান করতে হয়।
ডেটা তৈরি করুন
এই উদাহরণের ডেটা পূর্ববর্তী VRP উদাহরণের ডেটা অন্তর্ভুক্ত করে এবং নিম্নলিখিত চাহিদা এবং গাড়ির ক্ষমতা যোগ করে:
পাইথন
data["demands"] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8] data["vehicle_capacities"] = [15, 15, 15, 15]
সি++
const std::vector<int64_t> demands{
0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8,
};
const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15};জাভা
public final long[] demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8};
public final long[] vehicleCapacities = {15, 15, 15, 15};সি#
public long[] Demands = { 0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8 };
public long[] VehicleCapacities = { 15, 15, 15, 15 };ডেটাতে নতুন আইটেমগুলি হল:
- চাহিদা: প্রতিটি অবস্থানের পরিমাণের সাথে সঙ্গতিপূর্ণ চাহিদা রয়েছে- যেমন, ওজন বা আয়তন- যে আইটেমটি তোলা হবে।
- ক্ষমতা: প্রতিটি গাড়ির একটি ক্ষমতা আছে: গাড়িটি ধরে রাখতে পারে এমন সর্বাধিক পরিমাণ। একটি যানবাহন তার পথ ধরে চলার সময়, এটি বহন করা জিনিসের মোট পরিমাণ কখনই তার ধারণক্ষমতা অতিক্রম করতে পারে না।
দূরত্ব কলব্যাক যোগ করুন
দূরত্ব কলব্যাক—যে ফাংশন যে কোনো দুটি অবস্থানের মধ্যে দূরত্ব প্রদান করে—সেইভাবে পূর্ববর্তী VRP উদাহরণে সংজ্ঞায়িত করা হয়েছে।
চাহিদা কলব্যাক এবং ক্ষমতা সীমাবদ্ধতা যোগ করুন
দূরত্ব কলব্যাক ছাড়াও, সমাধানকারীর একটি চাহিদা কলব্যাক প্রয়োজন, যা প্রতিটি অবস্থানে চাহিদা ফেরত দেয় এবং ক্ষমতার সীমাবদ্ধতার জন্য একটি মাত্রা। নিম্নলিখিত কোড এগুলি তৈরি করে।
পাইথন
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",
)সি++
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");জাভা
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");সি#
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"); দূরত্বের কলব্যাকের বিপরীতে, যা ইনপুট হিসাবে এক জোড়া অবস্থান নেয়, চাহিদা কলব্যাক শুধুমাত্র ডেলিভারির অবস্থানের ( from_node ) উপর নির্ভর করে।
যেহেতু ধারণক্ষমতার সীমাবদ্ধতার সাথে একটি যানবাহন বহন করা বোঝার ওজন জড়িত — একটি পরিমাণ যা রুটে জমা হয় — আমাদের ধারণক্ষমতার জন্য একটি মাত্রা তৈরি করতে হবে, আগের VRP উদাহরণে দূরত্বের মাত্রার মতো।
এই ক্ষেত্রে, আমরা AddDimensionWithVehicleCapacity পদ্ধতি ব্যবহার করি, যা ক্যাপাসিটির একটি ভেক্টর নেয়।
যেহেতু এই উদাহরণে সমস্ত গাড়ির ক্ষমতা একই, আপনি AddDimension পদ্ধতি ব্যবহার করতে পারেন, যা সমস্ত যানবাহনের পরিমাণের জন্য একটি একক উপরের সীমা নেয়। কিন্তু AddDimensionWithVehicleCapacity আরও সাধারণ ক্ষেত্রে পরিচালনা করে যেখানে বিভিন্ন যানবাহনের বিভিন্ন ক্ষমতা থাকে।
একাধিক পণ্যসম্ভারের ধরন এবং ক্ষমতা নিয়ে সমস্যা
আরও জটিল CVRP-এ, প্রতিটি যানবাহন বিভিন্ন ধরণের পণ্যসম্ভার বহন করতে পারে, প্রতিটি প্রকারের জন্য সর্বাধিক ক্ষমতা সহ। উদাহরণস্বরূপ, একটি জ্বালানী বিতরণ ট্রাক বিভিন্ন ধরণের জ্বালানী বহন করতে পারে, বিভিন্ন ক্ষমতা সহ একাধিক ট্যাঙ্ক ব্যবহার করে। এই ধরনের সমস্যাগুলি পরিচালনা করতে, প্রতিটি পণ্যসম্ভারের জন্য শুধুমাত্র একটি ভিন্ন ক্ষমতা কলব্যাক এবং মাত্রা তৈরি করুন (তাদের অনন্য নাম বরাদ্দ করা নিশ্চিত করুন)।
সমাধান প্রিন্টার যোগ করুন
সমাধান প্রিন্টার প্রতিটি গাড়ির রুট প্রদর্শন করে, তার ক্রমবর্ধমান লোড সহ: মোট পরিমাণ গাড়িটি তার রুটে থামার সময় বহন করছে।
পাইথন
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 = 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 = solution.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}")সি++
//! @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) {
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::stringstream 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";
}জাভা
/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
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);
}সি#
/// <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.
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);
}প্রধান ফাংশন
এই উদাহরণের প্রধান ফাংশন টিএসপি উদাহরণের সাথে খুব মিল, তবে উপরে বর্ণিত চাহিদা এবং ক্ষমতার মাত্রা যোগ করে।
কার্যক্রম পরিচালনা করছেন
সম্পূর্ণ প্রোগ্রামটি পরবর্তী বিভাগে দেখানো হয়েছে। আপনি যখন প্রোগ্রাম চালান, এটি নিম্নলিখিত আউটপুট প্রদর্শন করে:
Objective: 6208 Route for vehicle 0: 0 Load(0) -> 4 Load(0) -> 3 Load(4) -> 1 Load(6) -> 7 Load(7) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 14 Load(0) -> 16 Load(4) -> 10 Load(12) -> 9 Load(14) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 2: 0 Load(0) -> 12 Load(0) -> 11 Load(2) -> 15 Load(3) -> 13 Load(11) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 3: 0 Load(0) -> 8 Load(0) -> 2 Load(8) -> 6 Load(9) -> 5 Load(13) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Total Distance of all routes: 6208m Total Load of all routes: 60
একটি রুটে প্রতিটি অবস্থানের জন্য, আউটপুট দেখায়:
- অবস্থানের সূচক।
গাড়িটি অবস্থান থেকে প্রস্থান করার সময় মোট লোড বহন করে।
রুট নীচে দেখানো হয়.
সম্পূর্ণ প্রোগ্রাম
ক্যাপাসিটেটেড গাড়ির রাউটিং সমস্যার জন্য সম্পূর্ণ প্রোগ্রামগুলি নীচে দেখানো হয়েছে।
পাইথন
"""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, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
data["vehicle_capacities"] = [15, 15, 15, 15]
data["num_vehicles"] = 4
data["depot"] = 0
return data
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 = 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 = solution.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",
)
# 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.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
if __name__ == "__main__":
main()সি++
#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, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 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) {
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::stringstream 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 VrpCapacity() {
// 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");
// 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::VrpCapacity();
return EXIT_SUCCESS;
}জাভা
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 final class VrpCapacity {
private static final Logger logger = Logger.getLogger(VrpCapacity.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, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 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.
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");
// 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);
}
private VrpCapacity() {}
}সি#
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
using Google.Protobuf.WellKnownTypes; // Duration
/// <summary>
/// Minimal TSP using distance matrix.
/// </summary>
public class VrpCapacity
{
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, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 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.
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");
// 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);
}
}GitHub-এ অন্যান্য ধরনের সীমাবদ্ধতার সাথে যানবাহন রাউটিং সমস্যার বেশ কয়েকটি উদাহরণ রয়েছে (যেসব উদাহরণে তাদের নামে "vrp" আছে) দেখুন।
কোন সমস্যার কোন সমাধান না হলে কি হবে?
সীমাবদ্ধতার সাথে একটি রাউটিং সমস্যা, যেমন একটি CVRP, এর সম্ভাব্য সমাধান নাও হতে পারে - উদাহরণস্বরূপ, যদি পরিবহন করা আইটেমগুলির মোট পরিমাণ যানবাহনের মোট ক্ষমতার চেয়ে বেশি হয়। আপনি যদি এই ধরনের সমস্যা সমাধান করার চেষ্টা করেন, তাহলে সমাধানকারী একটি সম্পূর্ণ অনুসন্ধান চালাতে পারে যা এত বেশি সময় নেয় যে অবশেষে আপনাকে প্রোগ্রামটি ছেড়ে দিতে হবে এবং বাধা দিতে হবে।
সাধারণত এই একটি সমস্যা হবে না. কিন্তু সমস্যাটির কোনো সমাধান না থাকলে আপনার প্রোগ্রামকে দীর্ঘ সময় চালানো থেকে বিরত রাখার জন্য এখানে কয়েকটি উপায় রয়েছে:
- প্রোগ্রামে একটি সময়সীমা সেট করুন, যা কোনো সমাধান না পাওয়া গেলেও অনুসন্ধান বন্ধ করে দেয়। যাইহোক, মনে রাখবেন যে যদি সমস্যাটির একটি সমাধান থাকে যার জন্য দীর্ঘ অনুসন্ধানের প্রয়োজন হয়, তবে সমাধানটি খুঁজে পাওয়ার আগে প্রোগ্রামটি সময়সীমাতে পৌঁছাতে পারে।
- অবস্থান পরিদর্শন ড্রপ জন্য জরিমানা সেট. এটি সমাধানকারীকে একটি "সমাধান" ফেরত দেওয়ার অনুমতি দেয় যা সমস্যাটি অসম্ভাব্য হলে সমস্ত অবস্থান পরিদর্শন করে না। পেনাল্টি এবং ড্রপিং ভিজিট দেখুন।
সাধারণভাবে, প্রদত্ত সমস্যার সমাধান আছে কিনা তা বলা কঠিন। এমনকি একটি CVRP-এর জন্য যেখানে মোট চাহিদা মোট ক্ষমতার চেয়ে বেশি নয়, সমস্ত আইটেম যানবাহনে ফিট হবে কিনা তা নির্ধারণ করা একাধিক ন্যাপস্যাক সমস্যার একটি সংস্করণ।