تنظيم صفحاتك في مجموعات
يمكنك حفظ المحتوى وتصنيفه حسب إعداداتك المفضّلة.
من أكثر مهام التحسين شيوعًا توجيه المركبات، والهدف منها العثور على أفضل المسارات لأسطول المركبات التي تزور مجموعة من المواقع الجغرافية. عادة ما تعني كلمة "أفضل" المسارات التي أقل مسافة أو تكلفة إجمالية.
في ما يلي بعض الأمثلة على مشاكل التوجيه:
تريد شركة توصيل الطرود تعيين مسارات للسائقين لإجراء عمليات التسليم.
لنفترض أن هناك شركة تلفزيون كبلي تريد تعيين مسارات للفنيين لإجراء مكالمات خدمات منزلية.
تريد شركة مشاركة الرحلات تعيين مسارات للسائقين لاصطحاب الركاب
وإنزالهم.
إنّ أكثر مشاكل التوجيه شهرة هي مشكلة مندوب المبيعات المسافر (TSP):
ابحث عن أقصر طريق لمندوب المبيعات الذي يحتاج إلى زيارة العملاء في مواقع جغرافية مختلفة والعودة إلى نقطة البداية. يمكن تمثيل مقدّم خدمة الرموز المميزة بواسطة رسم بياني حيث تتوافق العُقد مع المواقع الجغرافية، وتشير الحواف (أو الأقواس) إلى التنقّل المباشر بين المواقع. على سبيل المثال، يُظهر الرسم البياني أدناه
مقدّم خدمة مع أربعة مواقع جغرافية فقط مسماة "أ" و"ب" و"ج" و"د".
يتم تحديد المسافة بين أي موقعين من خلال الرقم المجاور للحافة التي تربطهما.
من خلال حساب المسافات لجميع المسارات الممكنة، يمكنك معرفة أن
أقصر مسار هو ACDBA، حيث تبلغ المسافة الإجمالية 35 + 30 + 15 + 10 = 90.
تصبح المشكلة أكثر صعوبة عندما يكون هناك المزيد من المواقع. في المثال أعلاه، هناك
ستة مسارات فقط. ولكن إذا كانت هناك عشرة مواقع (لا تحسب
نقطة البداية)، فإن عدد المسارات هو 362880.
بالنسبة إلى 20 موقعًا جغرافيًا، سينتقل الرقم إلى 2432902008176640000.
سيضمن البحث الشامل عن جميع المسارات الممكنة العثور على الأقصر، إلا أن ذلك يستدعي حلًا حسابيًا لكل المجموعات ما عدا المجموعات الصغيرة. بالنسبة للمشكلات الأكبر، هناك حاجة إلى أساليب التحسين
للبحث بذكاء في مساحة الحل والعثور على الحل
الأمثل (أو شبه الأمثل).
ثمة إصدار أكثر عمومية من مقدّم خدمة الرموز المميّزة يتمثّل في مشكلة توجيه المركبة (VRP) حيث توجد مركبات متعدّدة. في معظم الحالات، تكون هناك قيود مفروضة على نماذج معاينة الفيديو (VRP): على سبيل المثال، قد تحتوي المركبات على السعات اللازمة لوزن أو حجم البضائع التي يمكن حملها، أو قد يُطلب من السائقين زيارة المواقع الجغرافية خلال فترات زمنية محدّدة يطلبها العملاء.
يمكن أن تحل أدوات OR حلول العديد من أنواع VRP، بما في ذلك ما يلي:
VRP مع فترات زمنية، حيث يجب أن تقوم المركبات بزيارة المواقع الجغرافية خلال فترات زمنية محددة.
VRP مع قيود على الموارد، مثل المساحة أو الموظفين
لتحميل المركبات وتفريغها في المستودع (نقطة البداية للمسارات).
VRP مع انخفاض في عدد الزيارات: عندما لا يكون مطلوبًا من المركبات زيارة جميع المواقع الجغرافية، ولكن يجب دفع عقوبة عن كل زيارة يتم إغفالها.
القيود على حل مشكلات توجيه المركبات
تعد مشكلات توجيه المركبات قابلة للحل بطبيعتها، حيث يتزايد طول الوقت اللازم لحلها بشكل كبير مع حجم المشكلة. بالنسبة للمشكلات الكبيرة بما فيه الكفاية، قد يستغرق الأمر OR-أدوات (أو أي برنامج توجيه آخر) سنوات للعثور على الحل الأمثل. نتيجة لذلك، تُرجع أدوات OR أحيانًا حلولاً جيدة، ولكنها ليست مثالية. للعثور على حل أفضل، عليك تغيير
خيارات البحث الخاصة بأداة الحلّ. للاطّلاع على مثال، راجِع تغيير استراتيجية البحث.
تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)
[null,null,["تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)"],[[["\u003cp\u003eVehicle routing focuses on finding optimal routes for vehicles to visit locations, minimizing distance or cost, with applications like delivery services and ride-sharing.\u003c/p\u003e\n"],["\u003cp\u003eThe Traveling Salesperson Problem (TSP) seeks the shortest route for one vehicle to visit all locations and return to the starting point, becoming computationally complex with more locations.\u003c/p\u003e\n"],["\u003cp\u003eOR-Tools addresses various Vehicle Routing Problems (VRPs), including TSP, VRP with capacity and time constraints, and VRP with resource limitations and potential dropped visits.\u003c/p\u003e\n"],["\u003cp\u003eSolving VRPs can be computationally challenging, with solution times increasing exponentially with problem size, sometimes resulting in good but not optimal solutions from OR-Tools.\u003c/p\u003e\n"],["\u003cp\u003eWhile specialized solvers like Concorde excel at large TSPs, OR-Tools provides a more versatile platform for routing problems with constraints beyond the basic TSP.\u003c/p\u003e\n"]]],["Vehicle routing problems (VRPs) involve finding optimal routes for vehicles visiting locations, often minimizing total distance or cost. The Traveling Salesperson Problem (TSP) is a specific VRP with one vehicle. Solving these problems involves searching possible routes, with complexity increasing exponentially with more locations. OR-Tools, a routing solver, addresses various VRPs, including those with capacity, time, resource, and penalty constraints. While not always finding the absolute optimal solution, OR-Tools provides good solutions and users can adjust search strategies for better results.\n"],null,["# Vehicle Routing\n\n| **Note:** While the routing solver in Google's OR-Tools is free, users who need an industrial-class service can use the [Google Maps Platform Route Optimization API](https://developers.google.com/maps/documentation/route-optimization). Check out the [source code for a sample web application](https://github.com/googlemaps/js-route-optimization-app).\n\nOne of the most common optimization tasks is *vehicle routing*, in which the\ngoal is to find the best routes for a fleet of vehicles visiting a set of\nlocations. Usually, \"best\" means routes with the least total distance or cost.\nHere are a few examples of routing problems:\n\n- A package delivery company wants to assign routes for drivers to make deliveries.\n- A cable TV company wants to assign routes for technicians to make residential service calls.\n- A ride-sharing company wants to assign routes for drivers to pick up and drop off passengers.\n\nThe most famous routing problem is the *Traveling Salesperson Problem* (TSP):\nfind the shortest route for a salesperson who needs to visit customers at\ndifferent locations and return to the starting point. A TSP can be represented\nby a graph, in which the nodes correspond to the locations, and the edges (or\narcs) denote direct travel between locations. For example, the graph below shows\na TSP with just four locations, labeled A, B, C, and D.\nThe distance between any two locations is given by the number next to the edge\njoining them.\n\nBy calculating the distances of all possible routes, you can see that the\nshortest route is ACDBA, for which the total distance is `35 + 30 + 15 + 10 = 90`.\n\nThe problem gets harder when there are more locations. In the example above,\nthere are just six routes. But if there are ten locations (not counting the\nstarting point), the number of routes is 362880.\nFor 20 locations, the number jumps to 2432902008176640000.\nAn exhaustive search of all possible routes would be guaranteed to find the\nshortest, but this is computationally intractable for all but small sets of\nlocations. For larger problems, optimization techniques are needed to\nintelligently search the solution space and find an optimal (or near-optimal)\nsolution.\n\nA more general version of the TSP is the vehicle routing problem (VRP),\nin which there are multiple vehicles. In most cases, VRPs have constraints: for\nexample, vehicles might have capacities for the maximum weight or volume of items they\ncan carry, or drivers might be required to visit locations during specified time windows\nrequested by customers.\n\nOR-Tools can solve many types of VRPs, including the following:\n\n- [Traveling Salesperson Problem](/optimization/routing/tsp), the classic routing problem in which there is just one vehicle.\n- [Vehicle routing problem](/optimization/routing/vrp), a generalisation of the TSP with multiple vehicles.\n- [VRP with capacity constraints](/optimization/routing/cvrp), in which vehicles have maximum capacities for the items they can carry.\n- [VRP with time windows](/optimization/routing/vrptw), where the vehicles must visit the locations in specified time intervals.\n- [VRP with resource constraints](/optimization/routing/cvrptw_resources), such as space or personnel to load and unload vehicles at the depot (the starting point for the routes).\n- [VRP with dropped visits](/optimization/routing/penalties), where the vehicles aren't required to visit all locations, but must pay a penalty for each visit that is dropped.\n\nLimitations on solving vehicle routing problems\n-----------------------------------------------\n\nVehicle routing problems are inherently intractable: the length of time it takes\nto solve them grows exponentially with the size of the problem. For sufficiently\nlarge problems, it could take OR-Tools (or any other routing software) years to\nfind the optimal solution. As a result, OR-Tools sometimes returns solutions\nthat are good, but not optimal. To find a better solution, change the search\noptions for the solver. See [Changing the search strategy](/optimization/routing/tsp#search_strategy)\nfor an example.\n| **Note:** We should add that there are other solvers, such as [Concorde](http://www.math.uwaterloo.ca/tsp/concorde.html), dedicated to solving very large TSPs to optimality, which surpass OR-Tools in that area. However, OR-Tools provides a better platform for solving more general routing problems that contain constraints beyond those of a pure TSP."]]
