যানবাহন রাউটিং সমস্যা (ভিআরপি) এর লক্ষ্য হল একাধিক যানবাহনের জন্য একটি নির্দিষ্ট স্থানে যাওয়ার জন্য সর্বোত্তম রুট খুঁজে বের করা। (যখন শুধুমাত্র একটি যানবাহন থাকে, তখন এটি ভ্রমণ বিক্রয়কর্মীর সমস্যাকে হ্রাস করে।)
কিন্তু VRP-এর জন্য "অনুকূল রুট" বলতে আমরা কী বুঝি? একটি উত্তর হল সর্বনিম্ন মোট দূরত্ব সহ রুট। যাইহোক, যদি অন্য কোন সীমাবদ্ধতা না থাকে, সর্বোত্তম সমাধান হল সমস্ত অবস্থানগুলি দেখার জন্য শুধুমাত্র একটি গাড়ি বরাদ্দ করা এবং সেই গাড়ির জন্য সংক্ষিপ্ততম রুট খুঁজে বের করা। এটি মূলত টিএসপির মতো একই সমস্যা।
সর্বোত্তম রুট সংজ্ঞায়িত করার একটি ভাল উপায় হল সমস্ত যানবাহনের মধ্যে দীর্ঘতম একক রুটের দৈর্ঘ্য কমিয়ে আনা। যত তাড়াতাড়ি সম্ভব সমস্ত ডেলিভারি সম্পূর্ণ করার লক্ষ্য থাকলে এটি সঠিক সংজ্ঞা। নীচের VRP উদাহরণটি এইভাবে সংজ্ঞায়িত সর্বোত্তম রুট খুঁজে পায়।
পরবর্তী বিভাগে, আমরা যানবাহনের উপর সীমাবদ্ধতা যোগ করে TSP সাধারণীকরণের অন্যান্য উপায় বর্ণনা করব, যার মধ্যে রয়েছে:
- ধারণক্ষমতার সীমাবদ্ধতা : যানবাহনগুলিকে তারা পরিদর্শন করা প্রতিটি স্থানে আইটেম তুলতে হবে, তবে সর্বোচ্চ বহন ক্ষমতা থাকতে হবে।
- টাইম উইন্ডো : প্রতিটি অবস্থান একটি নির্দিষ্ট সময় উইন্ডোর মধ্যে পরিদর্শন করা আবশ্যক।
ভিআরপি উদাহরণ
এই বিভাগটি একটি VRP-এর একটি উদাহরণ উপস্থাপন করে যার লক্ষ্য হল দীর্ঘতম একক রুটকে ছোট করা।
অনুরূপ আয়তক্ষেত্রাকার ব্লক দ্বারা গঠিত একটি শহরে তার গ্রাহকদের দেখার প্রয়োজন এমন একটি কোম্পানির কল্পনা করুন। শহরের একটি ডায়াগ্রাম নীচে দেখানো হয়েছে, কোম্পানির অবস্থানটি কালো রঙে চিহ্নিত করা হয়েছে এবং নীল রঙে পরিদর্শনের স্থানগুলি।
OR-Tools দিয়ে VRP উদাহরণ সমাধান করা
নিম্নলিখিত বিভাগগুলি ব্যাখ্যা করে কিভাবে OR-Tools দিয়ে VRP উদাহরণ সমাধান করা যায়।
ডেটা তৈরি করুন
নিম্নলিখিত ফাংশন সমস্যার জন্য ডেটা তৈরি করে।
পাইথন
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["num_vehicles"] = 4
data["depot"] = 0
return dataসি++
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 int num_vehicles = 4;
const RoutingIndexManager::NodeIndex depot{0};
};জাভা
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 int vehicleNumber = 4;
public final int depot = 0;
}সি#
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 int VehicleNumber = 4;
public int Depot = 0;
};ডেটার মধ্যে রয়েছে:
-
distance_matrix: মিটারে অবস্থানের মধ্যে দূরত্বের একটি বিন্যাস। -
num_vehicles: বহরে যানবাহনের সংখ্যা। -
depot: ডিপোর সূচী, অবস্থান যেখানে সমস্ত যানবাহন তাদের রুট শুরু এবং শেষ করে।
অবস্থান স্থানাঙ্ক
উদাহরণ সেট আপ করতে এবং দূরত্ব ম্যাট্রিক্স গণনা করতে, আমরা শহরের চিত্রে দেখানো অবস্থানগুলিতে নিম্নলিখিত x - y স্থানাঙ্কগুলি বরাদ্দ করেছি:
[(456, 320), # location 0 - the depot (228, 0), # location 1 (912, 0), # location 2 (0, 80), # location 3 (114, 80), # location 4 (570, 160), # location 5 (798, 160), # location 6 (342, 240), # location 7 (684, 240), # location 8 (570, 400), # location 9 (912, 400), # location 10 (114, 480), # location 11 (228, 480), # location 12 (342, 560), # location 13 (684, 560), # location 14 (0, 640), # location 15 (798, 640)] # location 16
নোট করুন যে অবস্থানের স্থানাঙ্কগুলি সমস্যা ডেটাতে অন্তর্ভুক্ত নয়: সমস্যাটি সমাধান করার জন্য আপনাকে যা প্রয়োজন তা হল দূরত্ব ম্যাট্রিক্স, যা আমরা প্রাক-গণনা করেছি। সমাধানের অবস্থানগুলি সনাক্ত করতে আপনার শুধুমাত্র অবস্থানের ডেটা প্রয়োজন, যেগুলি উপরের তালিকায় তাদের সূচকগুলি (0, 1, 2 ...) দ্বারা চিহ্নিত করা হয়েছে৷
এই এবং অন্যান্য উদাহরণে অবস্থান স্থানাঙ্ক এবং শহরের চিত্র দেখানোর মূল উদ্দেশ্য হল সমস্যা এবং এর সমাধানের একটি ভিজ্যুয়াল ডিসপ্লে প্রদান করা। কিন্তু এটি একটি VRP সমাধানের জন্য অপরিহার্য নয়।
সমস্যা সেট আপ করার সুবিধার জন্য, অবস্থানের মধ্যে দূরত্ব ম্যানহাটান দূরত্ব ব্যবহার করে গণনা করা হয়, যেখানে দুটি বিন্দু, ( x 1 , y 1 ) এবং ( x 2 , y 2 ) এর মধ্যকার দূরত্বকে সংজ্ঞায়িত করা হয় | x 1 - x 2 | + | y 1 - y 2 |। যাইহোক, এই সংজ্ঞা ব্যবহার করার কোন বিশেষ কারণ নেই। দূরত্ব গণনা করার জন্য আপনি আপনার সমস্যার জন্য সবচেয়ে উপযুক্ত যে কোনো পদ্ধতি ব্যবহার করতে পারেন। অথবা, আপনি Google দূরত্ব ম্যাট্রিক্স API ব্যবহার করে বিশ্বের যেকোন অবস্থানের জন্য একটি দূরত্ব ম্যাট্রিক্স পেতে পারেন। কিভাবে এটি করতে হয় তার একটি উদাহরণের জন্য দূরত্ব ম্যাট্রিক্স API দেখুন।
দূরত্ব কলব্যাক সংজ্ঞায়িত করুন
TSP উদাহরণের মতো, নিম্নলিখিত ফাংশনটি দূরত্ব কলব্যাক তৈরি করে, যা অবস্থানের মধ্যে দূরত্ব প্রদান করে এবং এটি সমাধানকারীর কাছে প্রেরণ করে। এটি আর্ক খরচও সেট করে, যা ভ্রমণের খরচ নির্ধারণ করে, আর্কসের দূরত্ব হতে।
পাইথন
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)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)সি++
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];
});
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);জাভা
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];
});
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);সি#
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];
});
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);দূরত্বের মাত্রা যোগ করুন
এই VRP সমাধান করার জন্য, আপনাকে একটি দূরত্বের মাত্রা তৈরি করতে হবে, যা প্রতিটি গাড়ির তার রুটে ভ্রমণ করা ক্রমবর্ধমান দূরত্ব গণনা করে। তারপরে আপনি প্রতিটি রুট বরাবর মোট দূরত্বের সর্বোচ্চের সমানুপাতিক খরচ সেট করতে পারেন। রাউটিং প্রোগ্রামগুলি একটি গাড়ির রুটে জমা হওয়া পরিমাণের ট্র্যাক রাখতে মাত্রা ব্যবহার করে। আরও বিস্তারিত জানার জন্য মাত্রা দেখুন।
নিম্নলিখিত কোডটি সমাধানকারীর AddDimension পদ্ধতি ব্যবহার করে দূরত্বের মাত্রা তৈরি করে। আর্গুমেন্ট transit_callback_index হল দূরত্ব_কলব্যাকের জন্য সূচক।
পাইথন
dimension_name = "Distance"
routing.AddDimension(
transit_callback_index,
0, # no slack
3000, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name,
)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)সি++
routing.AddDimension(transit_callback_index, 0, 3000,
true, // start cumul to zero
"Distance");
routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100);জাভা
routing.addDimension(transitCallbackIndex, 0, 3000,
true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);সি#
routing.AddDimension(transitCallbackIndex, 0, 3000,
true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
distanceDimension.SetGlobalSpanCostCoefficient(100); SetGlobalSpanCostCoefficient পদ্ধতিটি রুটের গ্লোবাল স্প্যানের জন্য একটি বড় সহগ ( 100 ) সেট করে, যা এই উদাহরণে রুটের দূরত্বের সর্বোচ্চ। এটি বৈশ্বিক স্প্যানকে উদ্দেশ্যমূলক ফাংশনের প্রধান ফ্যাক্টর করে তোলে, তাই প্রোগ্রামটি দীর্ঘতম রুটের দৈর্ঘ্য কমিয়ে দেয়।
সমাধান প্রিন্টার যোগ করুন
সমাধানটি প্রিন্ট করে এমন ফাংশনটি নীচে দেখানো হয়েছে।
পাইথন
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
max_route_distance = 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
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print(f"Maximum of the route distances: {max_route_distance}m")
সি++
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
int64_t max_route_distance{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};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
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";
max_route_distance = std::max(route_distance, max_route_distance);
}
LOG(INFO) << "Maximum of the route distances: " << max_route_distance << "m";
LOG(INFO) << "";
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 maxRouteDistance = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
logger.info(route + manager.indexToNode(index));
logger.info("Distance of the route: " + routeDistance + "m");
maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
}
logger.info("Maximum of the route distances: " + maxRouteDistance + "m");
}সি#
/// <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 maxRouteDistance = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
Console.Write("{0} -> ", manager.IndexToNode((int)index));
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);
maxRouteDistance = Math.Max(routeDistance, maxRouteDistance);
}
Console.WriteLine("Maximum distance of the routes: {0}m", maxRouteDistance);
}ফাংশনটি যানবাহনের রুট এবং রুটের মোট দূরত্ব প্রদর্শন করে।
বিকল্পভাবে, আপনি প্রথমে একটি তালিকা বা অ্যারেতে রুটগুলি সংরক্ষণ করতে পারেন এবং তারপরে সেগুলি মুদ্রণ করতে পারেন।
প্রধান ফাংশন
VRP প্রোগ্রামের প্রধান ফাংশনের বেশিরভাগ কোড আগের TSP উদাহরণের মতোই। সেই কোডের বর্ণনার জন্য TSP বিভাগটি দেখুন। নতুন কি দূরত্ব মাত্রা , উপরে বর্ণিত.
কার্যক্রম পরিচালনা করছেন
সম্পূর্ণ প্রোগ্রাম পরবর্তী বিভাগে দেখানো হয়. আপনি যখন প্রোগ্রামগুলি চালান, তারা নিম্নলিখিত আউটপুট প্রদর্শন করে:
Objective: 177500 Route for vehicle 0: 0 -> 9 -> 10 -> 2 -> 6 -> 5 -> 0 Distance of the route: 1712m Route for vehicle 1: 0 -> 16 -> 14 -> 8 -> 0 Distance of the route: 1484m Route for vehicle 2: 0 -> 7 -> 1 -> 4 -> 3 -> 0 Distance of the route: 1552m Route for vehicle 3: 0 -> 13 -> 15 -> 11 -> 12 -> 0 Distance of the route: 1552m Maximum of the route distances: 1712m
রুটের অবস্থানগুলি অবস্থানের তালিকায় তাদের সূচক দ্বারা চিহ্নিত করা হয়। সমস্ত রুট ডিপোতে শুরু এবং শেষ হয় ( 0 )।
নীচের চিত্রটি নির্ধারিত রুটগুলি দেখায়, যেখানে অবস্থান সূচকগুলি সংশ্লিষ্ট x - y স্থানাঙ্কে রূপান্তরিত হয়েছে৷
সম্পূর্ণ প্রোগ্রাম
দীর্ঘতম একক রুটকে ছোট করে এমন সম্পূর্ণ প্রোগ্রামগুলি নীচে দেখানো হয়েছে।
পাইথন
"""Simple Vehicles Routing Problem (VRP).
This is a sample using the routing library python wrapper to solve a VRP
problem.
A description of the problem can be found here:
http://en.wikipedia.org/wiki/Vehicle_routing_problem.
Distances are in meters.
"""
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["num_vehicles"] = 4
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
max_route_distance = 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
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print(f"Maximum of the route distances: {max_route_distance}m")
def main():
"""Entry point of the program."""
# 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 Distance constraint.
dimension_name = "Distance"
routing.AddDimension(
transit_callback_index,
0, # no slack
3000, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name,
)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
else:
print("No solution found !")
if __name__ == "__main__":
main()সি++
#include <algorithm>
#include <cstdint>
#include <sstream>
#include <vector>
#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 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 max_route_distance{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};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
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";
max_route_distance = std::max(route_distance, max_route_distance);
}
LOG(INFO) << "Maximum of the route distances: " << max_route_distance << "m";
LOG(INFO) << "";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
void VrpGlobalSpan() {
// 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 Distance constraint.
routing.AddDimension(transit_callback_index, 0, 3000,
true, // start cumul to zero
"Distance");
routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
if (solution != nullptr) {
PrintSolution(data, manager, routing, *solution);
} else {
LOG(INFO) << "No solution found.";
}
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::VrpGlobalSpan();
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.RoutingDimension;
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 java.util.logging.Logger;
/** Minimal VRP.*/
public class VrpGlobalSpan {
private static final Logger logger = Logger.getLogger(VrpGlobalSpan.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 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 maxRouteDistance = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
logger.info(route + manager.indexToNode(index));
logger.info("Distance of the route: " + routeDistance + "m");
maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
}
logger.info("Maximum of the route distances: " + maxRouteDistance + "m");
}
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 Distance constraint.
routing.addDimension(transitCallbackIndex, 0, 3000,
true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);
// Print solution on console.
printSolution(data, routing, manager, solution);
}
}সি#
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// Minimal TSP using distance matrix.
/// </summary>
public class VrpGlobalSpan
{
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 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 maxRouteDistance = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
Console.Write("{0} -> ", manager.IndexToNode((int)index));
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);
maxRouteDistance = Math.Max(routeDistance, maxRouteDistance);
}
Console.WriteLine("Maximum distance of the routes: {0}m", maxRouteDistance);
}
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 Distance constraint.
routing.AddDimension(transitCallbackIndex, 0, 3000,
true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
distanceDimension.SetGlobalSpanCostCoefficient(100);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
// Solve the problem.
Assignment solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
PrintSolution(data, routing, manager, solution);
}
}Google দূরত্ব ম্যাট্রিক্স API ব্যবহার করে
বিভাগটি দেখায় যে ঠিকানার দ্বারা বা অক্ষাংশ এবং দ্রাঘিমাংশ দ্বারা সংজ্ঞায়িত অবস্থানের যেকোন সেটের জন্য দূরত্ব ম্যাট্রিক্স তৈরি করতে কীভাবে Google দূরত্ব ম্যাট্রিক্স API ব্যবহার করতে হয়। আপনি অনেক ধরনের রাউটিং সমস্যার জন্য দূরত্ব ম্যাট্রিক্স গণনা করতে API ব্যবহার করতে পারেন।
API ব্যবহার করতে, আপনার একটি API কী প্রয়োজন। এখানে একটি প্রাপ্ত কিভাবে.
উদাহরণ
উদাহরণ হিসেবে, আমরা একটি পাইথন প্রোগ্রামের মধ্য দিয়ে যাব যা মেমফিস, টেনেসি শহরের 16টি অবস্থানের একটি সেটের জন্য দূরত্ব ম্যাট্রিক্স তৈরি করে। দূরত্ব ম্যাট্রিক্স হল একটি 16 x 16 ম্যাট্রিক্স যার i , j এন্ট্রি হল i এবং j অবস্থানের মধ্যে দূরত্ব। এখানে অবস্থানের ঠিকানা আছে.
data['addresses'] = ['3610+Hacks+Cross+Rd+Memphis+TN', # depot
'1921+Elvis+Presley+Blvd+Memphis+TN',
'149+Union+Avenue+Memphis+TN',
'1034+Audubon+Drive+Memphis+TN',
'1532+Madison+Ave+Memphis+TN',
'706+Union+Ave+Memphis+TN',
'3641+Central+Ave+Memphis+TN',
'926+E+McLemore+Ave+Memphis+TN',
'4339+Park+Ave+Memphis+TN',
'600+Goodwyn+St+Memphis+TN',
'2000+North+Pkwy+Memphis+TN',
'262+Danny+Thomas+Pl+Memphis+TN',
'125+N+Front+St+Memphis+TN',
'5959+Park+Ave+Memphis+TN',
'814+Scott+St+Memphis+TN',
'1005+Tillman+St+Memphis+TN'
]API অনুরোধ
একটি দূরত্ব ম্যাট্রিক্স API অনুরোধ নিম্নোক্ত সম্বলিত একটি দীর্ঘ স্ট্রিং:
- API ঠিকানা:
https://maps.googleapis.com/maps/api/distancematrix/json?. অনুরোধের শেষে,json, JSON-এ প্রতিক্রিয়া জানতে চায়। - অনুরোধ বিকল্প. এই উদাহরণে,
units=imperialইংরেজিতে প্রতিক্রিয়ার ভাষা সেট করে। - মূল ঠিকানা: ভ্রমণ শুরুর পয়েন্ট। যেমন
&origins=3610+Hacks+Cross+Rd+Memphis+TN।
ঠিকানার স্থানগুলি+অক্ষর দিয়ে প্রতিস্থাপিত হয়। একাধিক ঠিকানা একটি|দ্বারা পৃথক করা হয় . - গন্তব্য ঠিকানা: ভ্রমণ শেষ পয়েন্ট। উদাহরণস্বরূপ
&destinations=3734+Elvis+Presley+Blvd+Memphis+TN - API কী: অনুরোধের শংসাপত্র, ফর্মে
&key=YOUR_API_KEY।
এখানে "অরিজিন ঠিকানা" এবং "গন্তব্য ঠিকানা" এর পরে উপরে দেখানো একক উত্স এবং একক গন্তব্যের জন্য সম্পূর্ণ অনুরোধ রয়েছে৷
https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial&origins=3610+Hacks+Cross+Rd+Memphis+TN&destinations=3734+Elvis+Presley+Blvd+Memphis+TN&key=YOUR_API_KEY
এখানে অনুরোধের প্রতিক্রিয়া.
{
"destination_addresses" : [ "1921 Elvis Presley Blvd, Memphis, TN 38106, USA" ],
"origin_addresses" : [ "3610 Hacks Cross Rd, Memphis, TN 38125, USA" ],
"rows" : [
{
"elements" : [
{
"distance" : {
"text" : "15.2 mi",
"value" : 24392
},
"duration" : {
"text" : "21 mins",
"value" : 1264
},
"status" : "OK"
}
]
}
],
"status" : "OK"
}
প্রতিক্রিয়াটিতে দুটি ঠিকানার মধ্যে ভ্রমণের দূরত্ব (মাইল এবং মিটারে), এবং ভ্রমণের সময়কাল (মিনিট এবং সেকেন্ডে) রয়েছে।
অনুরোধ এবং প্রতিক্রিয়া সম্পর্কে বিস্তারিত জানার জন্য দূরত্ব ম্যাট্রিক্স API ডকুমেন্টেশন দেখুন।
দূরত্ব ম্যাট্রিক্স গণনা করুন
দূরত্ব ম্যাট্রিক্স গণনা করার জন্য, আমরা মূল এবং গন্তব্য ঠিকানা উভয় হিসাবে 16টি ঠিকানা সহ একটি একক অনুরোধ পাঠাতে চাই। যাইহোক, আমরা পারি না কারণ এর জন্য 16x16=256 অরিজিন-গন্তব্য জোড়ার প্রয়োজন হবে, যখন API অনুরোধ প্রতি 100 টি জোড়ার মধ্যে সীমাবদ্ধ। তাই আমাদের একাধিক অনুরোধ করতে হবে।
যেহেতু ম্যাট্রিক্সের প্রতিটি সারিতে 16টি এন্ট্রি রয়েছে, তাই আমরা প্রতি অনুরোধে সর্বাধিক ছয়টি সারি গণনা করতে পারি ( 6x16=96 জোড়া প্রয়োজন)। আমরা তিনটি অনুরোধে সম্পূর্ণ ম্যাট্রিক্স গণনা করতে পারি, যা 6টি সারি, 6টি সারি এবং 4টি সারি প্রদান করে।
নিম্নলিখিত কোডটি নিম্নরূপ দূরত্ব ম্যাট্রিক্স গণনা করে:
- 16টি ঠিকানাকে ছয়টি ঠিকানার দুটি দলে এবং চারটি ঠিকানার একটি দলে ভাগ করুন।
- প্রতিটি গ্রুপের জন্য, গ্রুপে মূল ঠিকানা এবং সমস্ত গন্তব্য ঠিকানার জন্য একটি অনুরোধ তৈরি করুন এবং পাঠান। বিল্ড দেখুন এবং একটি অনুরোধ পাঠান ।
- ম্যাট্রিক্সের সংশ্লিষ্ট সারিগুলি তৈরি করতে প্রতিক্রিয়াটি ব্যবহার করুন এবং সারিগুলিকে সংযুক্ত করুন (যা কেবল পাইথন তালিকা)। দূরত্ব ম্যাট্রিক্সের সারি তৈরি করুন দেখুন।
def create_distance_matrix(data):
addresses = data["addresses"]
API_key = data["API_key"]
# Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.
max_elements = 100
num_addresses = len(addresses) # 16 in this example.
# Maximum number of rows that can be computed per request (6 in this example).
max_rows = max_elements // num_addresses
# num_addresses = q * max_rows + r (q = 2 and r = 4 in this example).
q, r = divmod(num_addresses, max_rows)
dest_addresses = addresses
distance_matrix = []
# Send q requests, returning max_rows rows per request.
for i in range(q):
origin_addresses = addresses[i * max_rows: (i + 1) * max_rows]
response = send_request(origin_addresses, dest_addresses, API_key)
distance_matrix += build_distance_matrix(response)
# Get the remaining remaining r rows, if necessary.
if r > 0:
origin_addresses = addresses[q * max_rows: q * max_rows + r]
response = send_request(origin_addresses, dest_addresses, API_key)
distance_matrix += build_distance_matrix(response)
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.urlopen(request).read()
response = json.loads(jsonResult)
return response সাব-ফাংশন build_address_string পাইপ অক্ষর, | দ্বারা পৃথক করা ঠিকানাগুলিকে সংযুক্ত করে .
ফাংশনের অবশিষ্ট কোড উপরে বর্ণিত অনুরোধের অংশগুলিকে একত্রিত করে এবং অনুরোধ পাঠায়। লাইন
response = json.loads(jsonResult)
কাঁচা ফলাফলকে পাইথন অবজেক্টে রূপান্তর করে।
ম্যাট্রিক্সের সারি তৈরি করুন
নিম্নলিখিত ফাংশন send_request ফাংশন দ্বারা প্রত্যাবর্তিত প্রতিক্রিয়া ব্যবহার করে দূরত্ব ম্যাট্রিক্সের সারি তৈরি করে।
def build_distance_matrix(response):
distance_matrix = []
for row in response['rows']:
row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
distance_matrix.append(row_list)
return distance_matrixলাইন
row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
প্রতিক্রিয়ার একটি সারির জন্য অবস্থানের মধ্যে দূরত্ব বের করে। আপনি এটিকে একটি একক উত্স এবং গন্তব্যের জন্য প্রতিক্রিয়ার একটি অংশের সাথে ( json.loads দ্বারা রূপান্তরিত) তুলনা করতে পারেন, নীচে দেখানো হয়েছে৷
{u'status': u'OK', u'rows':
[{u'elements': [{u'duration': {u'text': u'21 mins', u'value': 1264},
u'distance': {u'text': u'15.2 mi', u'value': 24392},
u'status': u'OK'}]}],
u'origin_addresses': [u'3610 Hacks Cross Rd, Memphis, TN 38125, USA'],
u'destination_addresses': [u'1921 Elvis Presley Blvd, Memphis, TN 38106, USA']}
আপনি যদি একটি টাইম ম্যাট্রিক্স তৈরি করতে চান, যেখানে অবস্থানের মধ্যে ভ্রমণের সময় থাকে, তাহলে 'distance' 'duration' দিয়ে প্রতিস্থাপন করুন build_distance_matrix ফাংশনে।
প্রোগ্রাম চালান
প্রধান ফাংশনে নিম্নলিখিত কোডটি প্রোগ্রামটি চালায়
def main(): """Entry point of the program""" # Create the data. data = create_data() addresses = data['addresses'] API_key = data['API_key'] distance_matrix = create_distance_matrix(data) print(distance_matrix)
আপনি যখন প্রোগ্রামটি চালান, তখন এটি দূরত্ব ম্যাট্রিক্স প্রিন্ট করে, যেমনটি নীচে দেখানো হয়েছে।
[[0, 24392, 33384, 14963, 31992, 32054, 20866, 28427, 15278, 21439, 28765, 34618, 35177, 10612, 26762, 27278], [25244, 0, 8314, 10784, 6922, 6984, 10678, 3270, 10707, 7873, 11350, 9548, 10107, 19176, 12139, 13609], [34062, 8491, 0, 14086, 4086, 1363, 11008, 4239, 13802, 9627, 7179, 1744, 925, 27994, 9730, 10531], [15494, 13289, 13938, 0, 11065, 12608, 4046, 10970, 581, 5226, 10788, 15500, 16059, 5797, 9180, 9450], [33351, 7780, 4096, 11348, 0, 2765, 7364, 4464, 11064, 6736, 3619, 4927, 5485, 20823, 6170, 7076], [32731, 7160, 1363, 12755, 2755, 0, 9677, 3703, 12471, 8297, 7265, 2279, 2096, 26664, 9816, 9554], [19636, 10678, 11017, 4038, 7398, 9687, 0, 9159, 3754, 2809, 7099, 10740, 11253, 8970, 5491, 5928], [29097, 3270, 4257, 11458, 4350, 3711, 9159, 0, 11174, 6354, 10160, 5178, 5258, 23029, 10620, 12419], [15809, 10707, 13654, 581, 10781, 12324, 3763, 10687, 0, 4943, 10504, 15216, 15775, 5216, 8896, 9166], [21831, 7873, 9406, 5226, 6282, 8075, 2809, 6354, 4943, 0, 6967, 10968, 11526, 10159, 5119, 6383], [28822, 11931, 6831, 11802, 3305, 6043, 7167, 10627, 11518, 7159, 0, 5361, 6422, 18351, 3267, 4068], [35116, 9545, 1771, 15206, 4648, 2518, 10967, 5382, 14922, 10747, 5909, 0, 1342, 29094, 8460, 9260], [36058, 10487, 927, 16148, 5590, 2211, 11420, 9183, 15864, 11689, 6734, 1392, 0, 30036, 9285, 10086], [11388, 19845, 28838, 5797, 20972, 27507, 8979, 23880, 5216, 10159, 18622, 29331, 29890, 0, 16618, 17135], [27151, 11444, 9719, 10131, 6193, 8945, 5913, 10421, 9847, 5374, 3335, 8249, 9309, 16680, 0, 1264], [27191, 14469, 10310, 9394, 7093, 9772, 5879, 13164, 9110, 6422, 3933, 8840, 9901, 16720, 1288, 0]]
ভ্রমণের সময় ম্যাট্রিক্স
উপরে উল্লিখিত হিসাবে, আপনি অবস্থানগুলির মধ্যে ভ্রমণের সময়ের একটি ম্যাট্রিক্স তৈরি করতে চান (দূরত্বের পরিবর্তে), কেবল 'distance' 'duration' দিয়ে প্রতিস্থাপন করুন build_distance_matrix ফাংশনে। আপনি যখন সেই পরিবর্তনের সাথে প্রোগ্রামটি চালান, তখন এটি নিম্নলিখিত ভ্রমণের সময় ম্যাট্রিক্স প্রদর্শন করে:
[[0, 1232, 1599, 964, 1488, 1441, 1291, 1323, 978, 1228, 1493, 1617, 1570, 765, 1272, 1359], [1333, 0, 653, 922, 542, 495, 864, 297, 917, 622, 783, 671, 624, 1059, 985, 904], [1669, 643, 0, 1291, 447, 161, 1021, 461, 1258, 862, 715, 419, 198, 1395, 855, 904], [1062, 862, 1262, 0, 946, 1104, 360, 926, 61, 482, 995, 1237, 1190, 589, 761, 839], [1626, 600, 475, 1008, 0, 317, 688, 505, 976, 630, 446, 475, 428, 1271, 587, 648], [1537, 511, 166, 1158, 314, 0, 889, 402, 1125, 730, 697, 430, 313, 1262, 837, 770], [1388, 891, 1022, 374, 668, 863, 0, 731, 341, 259, 731, 1110, 1091, 869, 496, 570], [1407, 303, 489, 934, 492, 410, 725, 0, 901, 482, 692, 580, 587, 1132, 845, 814], [1060, 914, 1215, 55, 899, 1057, 314, 880, 0, 435, 949, 1190, 1144, 528, 714, 792], [1314, 651, 855, 475, 605, 696, 260, 491, 443, 0, 700, 830, 783, 970, 489, 596], [1530, 801, 697, 990, 427, 625, 709, 721, 957, 663, 0, 542, 634, 1084, 338, 387], [1704, 678, 370, 1355, 508, 430, 1074, 598, 1322, 866, 564, 0, 297, 1405, 703, 752], [1612, 586, 215, 1201, 416, 359, 1070, 506, 1169, 773, 639, 313, 0, 1312, 778, 827], [861, 1074, 1441, 610, 1337, 1282, 869, 1164, 555, 990, 1157, 1433, 1386, 0, 936, 1022], [1375, 1045, 899, 795, 629, 825, 588, 901, 762, 549, 408, 744, 836, 929, 0, 107], [1428, 947, 957, 885, 692, 750, 599, 867, 852, 637, 362, 803, 894, 982, 111, 0]]
একটি VRP প্রোগ্রামে দূরত্ব ম্যাট্রিক্স ব্যবহার করা
একটি ভিআরপি প্রোগ্রামে উপরে দেখানো দূরত্ব ম্যাট্রিক্সটি কীভাবে ব্যবহার করবেন তা দেখতে, পূর্ববর্তী ভিআরপি উদাহরণের দূরত্ব ম্যাট্রিক্সটিকে উপরের একটি দিয়ে প্রতিস্থাপন করুন। এছাড়াও, দূরত্বের মাত্রার maximum_distance প্যারামিটারের মান 70000 এ পরিবর্তন করুন। আপনি যখন পরিবর্তিত প্রোগ্রাম চালান, এটি নিম্নলিখিত আউটপুট প্রদান করে।
Route for vehicle 0: 0 -> 1 -> 7 -> 5 -> 4 -> 8 -> 0 Distance of route: 61001m Route for vehicle 1: 0 -> 0 Distance of route: 0m Route for vehicle 2: 0 -> 3 -> 2 -> 12 -> 11 -> 6 -> 0 Distance of route: 61821m Route for vehicle 3: 0 -> 13 -> 9 -> 10 -> 14 -> 15 -> 0 Distance of route: 59460m Total distance of all routes: 182282m
পুরো প্রোগ্রাম
সম্পূর্ণ প্রোগ্রাম নীচে দেখানো হয়.
import requests
import json
import urllib
def create_data():
"""Creates the data."""
data = {}
data['API_key'] = 'YOUR_API_KEY'
data['addresses'] = ['3610+Hacks+Cross+Rd+Memphis+TN', # depot
'1921+Elvis+Presley+Blvd+Memphis+TN',
'149+Union+Avenue+Memphis+TN',
'1034+Audubon+Drive+Memphis+TN',
'1532+Madison+Ave+Memphis+TN',
'706+Union+Ave+Memphis+TN',
'3641+Central+Ave+Memphis+TN',
'926+E+McLemore+Ave+Memphis+TN',
'4339+Park+Ave+Memphis+TN',
'600+Goodwyn+St+Memphis+TN',
'2000+North+Pkwy+Memphis+TN',
'262+Danny+Thomas+Pl+Memphis+TN',
'125+N+Front+St+Memphis+TN',
'5959+Park+Ave+Memphis+TN',
'814+Scott+St+Memphis+TN',
'1005+Tillman+St+Memphis+TN'
]
return data
def create_distance_matrix(data):
addresses = data["addresses"]
API_key = data["API_key"]
# Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.
max_elements = 100
num_addresses = len(addresses) # 16 in this example.
# Maximum number of rows that can be computed per request (6 in this example).
max_rows = max_elements // num_addresses
# num_addresses = q * max_rows + r (q = 2 and r = 4 in this example).
q, r = divmod(num_addresses, max_rows)
dest_addresses = addresses
distance_matrix = []
# Send q requests, returning max_rows rows per request.
for i in range(q):
origin_addresses = addresses[i * max_rows: (i + 1) * max_rows]
response = send_request(origin_addresses, dest_addresses, API_key)
distance_matrix += build_distance_matrix(response)
# Get the remaining remaining r rows, if necessary.
if r > 0:
origin_addresses = addresses[q * max_rows: q * max_rows + r]
response = send_request(origin_addresses, dest_addresses, API_key)
distance_matrix += build_distance_matrix(response)
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.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]['distance']['value'] for j in range(len(row['elements']))]
distance_matrix.append(row_list)
return distance_matrix
########
# Main #
########
def main():
"""Entry point of the program"""
# Create the data.
data = create_data()
addresses = data['addresses']
API_key = data['API_key']
distance_matrix = create_distance_matrix(data)
print(distance_matrix)
if __name__ == '__main__':
main()