टैक्सी आंदोलनों की गणना

Question

मान लें कि मेरे पास एन टैक्सियां ​​हैं, और एन ग्राहक टैक्सियों द्वारा उठाए जाने की प्रतीक्षा कर रहे हैं। दोनों ग्राहकों और टैक्सियों की शुरुआती स्थिति यादृच्छिक/मनमानी हैं।

अब मैं प्रत्येक टैक्सी को बिल्कुल एक ग्राहक को असाइन करना चाहता हूं।

ग्राहक सभी स्थिर हैं, और टैक्सी सभी समान गति से आगे बढ़ते हैं। सादगी के लिए, मान लीजिए कि कोई बाधा नहीं है, और टैक्सियों को सीधे ग्राहकों को सौंपा गया है।

अब मैं उस समय को कम करना चाहता हूं जब तक कि अंतिम ग्राहक अपनी टैक्सी में प्रवेश न करे।

क्या इसे हल करने के लिए मानक एल्गोरिदम है? मेरे पास हजारों टैक्सी/ग्राहक हैं। समाधान इष्टतम नहीं होना चाहिए, बस 'अच्छा'।

समस्या को मानक "असाइनमेंट समस्या" के रूप में लगभग मॉडल किया जा सकता है, Hungarian algorithm (कुह्न-मंक्रेस एल्गोरिदम या मंक्रेस असाइनमेंट एल्गोरिदम) का उपयोग करके हल करने योग्य। हालांकि, मैं सबसे महंगी असाइनमेंट की लागत को कम करना चाहता हूं, असाइनमेंट की लागत को कम नहीं करता हूं।

Answer 1

पाया जा सकता है आप हंगेरी एल्गोरिथ्म उल्लेख के बाद से, मैं एक बात आप और बजाय दूरी से कुछ अलग उपाय इयूक्लिडियन दूरी उपयोग कर रहा है कर सकता है तो उस पर हंगरी एल्गोरिथ्म टी चलाने लगता है। उदाहरण के लिए, बजाय

d = sqrt का उपयोग कर के ((x0 - x 1)^2 + (y1 - Y0)^2)

उपयोग

d = ((x0 - x 1)^2 + (वाई 1 - वाई 0)^2)^10

जो एल्गोरिदम को बड़ी संख्या में दंडित करने का कारण बन सकता है, जो अधिकतम दूरी की लंबाई को बाधित कर सकता है।

संपादित करें: इस पत्र "ज्यामिति टोंटी मिलान में मदद करता है और संबंधित समस्याएं" मई एक बेहतर एल्गोरिथ्म शामिल हैं। हालांकि, मैं अभी भी इसे पढ़ने की प्रक्रिया में हूं।

Answer 2

आपकी समस्या का समाधान करने वाला एक "अच्छा" एल्गोरिदम Greedy Algorithm है। चूंकि टैक्सियों और लोगों की स्थिति होती है, इसलिए इन पदों को "केंद्रीय" स्थान से जोड़ा जा सकता है। टैक्सियों और लोगों को व्यवस्थित करने की आवश्यकता है ("केंद्र" के संबंध में)। फिर क्रम में लोगों को लेने के लिए टैक्सियों को असाइन करना शुरू करें। यह लालची नियम यह सुनिश्चित करेगा कि केंद्र के सबसे करीबी टैक्सियों को केंद्र के सबसे नज़दीकी लोगों को उठाया जाएगा और टैक्सियों ने सबसे दूर लोगों को दूर से दूर ले जाया है।

Dynamic Programming का उपयोग करने का एक बेहतर तरीका हो सकता है, मुझे यकीन नहीं है कि न ही निवेश करने का समय है। गतिशील प्रोग्रामिंग के लिए एक अच्छा ट्यूटोरियल here

Answer 3

सर्वोत्कृष्ट समाधान के लिए: प्रत्येक टैक्सी और ग्राहक और प्रत्येक ग्राहक जिसका वजन यात्रा के समय है करने के लिए प्रत्येक टैक्सी से एक बढ़त के लिए एक शीर्ष के साथ एक भारित द्विपक्षीय ग्राफ का निर्माण। Nondecreasing वजन के क्रम में किनारों को स्कैन करें, अधिकतम को बनाए गए किनारों वाले मिलान वाले उपग्राफ के मिलान को बनाए रखें। जब मिलान सही है तो रोकें।

Answer 4

मुझे यकीन नहीं है कि हंगेरियन एल्गोरिदम आपकी समस्या के लिए यहां काम करेगा। लिंक के अनुसार, यह एन^3 समय में चलता है। 25,000 में एन के रूप में प्लगिंग 25,000^3 = 15,625,000,000,000 उत्पन्न करेगा। इसे चलाने में काफी समय लग सकता है।

चूंकि समाधान को इष्टतम होने की आवश्यकता नहीं है, इसलिए आप simulated annealing या संभवतः genetic algorithm का उपयोग करने पर विचार कर सकते हैं। इनमें से कोई भी बहुत तेज होना चाहिए और अभी भी इष्टतम समाधान के करीब उत्पादन करना चाहिए।

यदि आनुवंशिक एल्गोरिदम का उपयोग करते हैं, तो फिटनेस फ़ंक्शन को उस समय की सबसे लंबी अवधि को कम करने के लिए डिज़ाइन किया जा सकता है जिसे किसी व्यक्ति को प्रतीक्षा करने की आवश्यकता होगी। लेकिन, आपको सावधान रहना होगा क्योंकि यदि यह एकमात्र मानदंड है, तो समाधान उन मामलों के लिए बहुत अच्छा काम नहीं करेगा जब केवल एक कैब है जो यात्री से निकटतम है। इसलिए, फिटनेस फ़ंक्शन को अन्य प्रतीक्षा समयों को भी ध्यान में रखना होगा। इसे हल करने का एक विचार यह होगा कि मॉडल को क्रमशः चलाने के लिए और प्रत्येक पुनरावृत्ति के बाद सबसे लंबी कैब यात्रा (दोनों कैब & व्यक्ति) को हटा दें। लेकिन, ऐसा करने के लिए सभी 10,000+ कैब/लोग महंगे समय के अनुसार हो सकते हैं।

मुझे नहीं लगता कि कोई भी कैब मालिक या प्रबंधक सभी कैब के लिए प्रतीक्षा समय के योग को कम करने के लिए अपने ग्राहक को अपने कैब में प्रवेश करने के लिए प्रतीक्षा समय को कम करने पर भी विचार करेगा - क्योंकि वे कम से कम अधिक पैसा कमाते हैं प्रतीक्षा समय का योग। कम से कम Louie DePalma ऐसा कभी नहीं करेगा ... तो, मुझे संदेह है कि आपके पास असली समस्या है या कैब के साथ कुछ भी नहीं है ...