التوجيه الأمثل للخريطة باستخدام خرائط Google

Question

هل هناك طريقة تستخدم واجهة برمجة التطبيقات لخرائط Google لاستعادة مسار "مُحسَّن" في ضوء مجموعة من نقاط الطريق (بعبارة أخرى، حل "جيد بما فيه الكفاية" لمشكلة البائع المتجول)، أم أنها تُرجع المسار دائمًا مع النقاط بالترتيب المحدد؟

Answer 1

وكان دائما يعطي لهم في النظام.

لذلك أعتقد أن عليك أن تجد المسافة (أو الوقت) بين كل زوج من النقاط، واحد في كل مرة، ثم حل المشكلة السفر بائع نفسك. ربما يمكن أن تقنع خرائط جوجل لإضافة هذه الميزة على الرغم من. أعتقد أن ما يشكل "جيدة بما فيه الكفاية" حل يعتمد على ما تفعلونه ومدى سرعة يحتاج أن يكون.

Answer 2

وهناك خيار في خرائط Google API DirectionsRequest دعا optimizeWaypoints، والتي ينبغي أن تفعل ما تريد. هذا يمكن فقط التعامل مع ما يصل إلى 8 نقاط الطريق، وإن كان.

وبدلا من ذلك، هناك مفتوح المصدر (رخصة MIT) مكتبة التي يمكنك استخدامها مع API خرائط جوجل للحصول على الأمثل (تصل إلى 15 موقعا) أو قريبة جدا لالأمثل (حتى 100 موقع) الطريق.

http://code.google.com/p/google- خرائط-ملعقة شاي حلالا /

ويمكنك أن ترى المكتبة في العمل على www.optimap.net

Answer 3

في مشكلة TSP نموذجية، فإن الافتراض هو واحد يمكن السفر مباشرة بين أي نقطتين. للطرق السطح، وهذا هو الحال أبدا. عندما يحسب جوجل طريق بين نقطتين، فإنه يقوم ارشادي تمتد الأمثل شجرة، وعادة ما تأتي مع وثيقة إلى حد ما المسار الأمثل.

لحساب مسار TSP، فإن المرء لابد أولا أن نسأل جوجل لحساب المسافة بين الزوج الحكيم كل عقدة في الرسم البياني. وأعتقد أن هذا يتطلب ن * (ن 1) / 2 calcs. ويمكن للمرء ثم تأخذ تلك المسافات وإجراء التحسين TSP عليها.

وOpenStreetMaps.org لديه تطبيق جافا webstart و التي قد تفعل ما تريد. وبطبيعة الحال يتم تشغيل حسابات العميل. مشروع مفتوح المصدر، وربما يكون من المفيد إلقاء نظرة.

هل تحاول العثور على المسار الأمثل التوالي الخط الفاصل بين المواقع، أو الطريق القيادة الأمثل؟ إذا كنت ترغب فقط في أمر النقاط، إذا كان يمكنك الحصول على إحداثيات GPS، يصبح مشكلة سهلة للغاية.

Answer 4

http://gebweb.net/optimap/ يبدو لطيفا وسهل. النسخة الإلكترونية باستخدام خرائط جوجل.

Answer 5

جوجل لديها حل جاهز لمشكلة بائع السفر.إنها أدوات OR (أدوات أبحاث العمليات من Google) التي يمكنك العثور عليها هنا: https://developers.google.com/optimization/routing/tsp

ما عليك القيام به بشكل أساسي هو شيئين:

• احصل على المسافات بين كل نقطتين باستخدام Google Maps API: https://developers.google.com/maps/documentation/distance-matrix/start

• بعد ذلك سوف تقوم بتغذية المسافات في صفيف إلى أو-أدوات وسوف يجد لك حلاً جيدًا جدًا (بالنسبة لبعض الحالات التي تحتوي على ملايين العقد، تم العثور على حلول مضمونة في حدود 1% من الجولة المثالية).

يمكنك أيضًا ملاحظة ما يلي:

بالإضافة إلى إيجاد حلول لمشكلة بائع السفر الكلاسيكية ، توفر الأدوات أيضًا طرقًا لمزيد من أنواع TSPs ، بما في ذلك ما يلي:

• مشاكل التكلفة غير المتماثلة - TSP التقليدي متماثل:المسافة من النقطة أ إلى النقطة ب تساوي المسافة من النقطة ب إلى النقطة أ.ومع ذلك ، فإن تكلفة شحن عناصر من النقطة أ إلى النقطة ب قد لا تساوي تكلفة شحنها من النقطة ب إلى النقطة أ.يمكن لأدوات OR أيضًا التعامل مع المشكلات ذات التكاليف غير المتماثلة.

• مقدمو خدمات TSP الذين يجمعون الجوائز، حيث تتراكم الفوائد من زيارة العقد

• TSP مع نوافذ زمنية

روابط إضافية:

• أدوات OR في Github: https://github.com/google/or-tools
• البدء: https://developers.google.com/optimization/introduction/get_started