मार्ग अनुकूलन के साथ संचालन में सुधार

योगदानकर्ता: फीको लाइ, मिशाल स्ज़ेसकिन्स्की, विनी सो, मिगुएल फ़र्नांडीज़

हर दिन, GOGOVAN ड्राइवर एशिया भर के गोदामों में पहुंचते हैं ताकि हमारे ऑर्डर को अपने क्लाइंट तक पहुंचाने के लिए हजारों ऑर्डर मिलें।

ये आदेश कई चीजों की श्रेणी हो सकते हैं - उस लंबे समय से प्रतीक्षित नए फोन से, एक सालगिरह तक जिसे अंतिम मिनट में आदेश दिया गया था। ये सभी अलग-अलग आकार, आकार और वजन के होंगे। उनमें से हर एक के लिए, एक व्यक्ति इंतजार कर रहा होगा और उम्मीद कर रहा है कि इस समय कूरियर कंपनी को समय पर मिल जाएगा ...

यही कारण है कि GOGOVAN में, हम अपने ग्राहकों की सेवा को विस्मित करने वाली गुणवत्ता के साथ सुचारू और समय पर वितरण सुनिश्चित करने के लिए अपनी शक्ति में सब कुछ करते हैं। प्रत्येक वितरण मार्ग को सावधानीपूर्वक मैन्युअल रूप से योजनाबद्ध किया गया है और हमारी संचालन टीम द्वारा डबल-चेक किया गया है, यह सुनिश्चित करने के लिए कि हम कभी असफल नहीं होते हैं।

मैन्युअल ?!

क्या आपको लगता है कि आप उन आदेशों का पालन नहीं कर सकते हैं?

हां यह सही है।

अतीत में, ऑपरेशन टीम को आमतौर पर पिकअप की सुबह डिलीवरी मार्गों को मैन्युअल रूप से सुलझाना होता था, और हम उस दिन के लिए डिलीवरी की सभी आवश्यकताओं को पूरा करना सुनिश्चित करते हैं। जैसा कि आप सोच सकते हैं, कि एक विशेष रूप से रोमांचक या आसान काम नहीं है :)

100 वेपाइंट के लिए एक उप-इष्टतम मार्ग बनाने में लगभग 1 घंटे का समय लगा। इससे बड़े अनुरोधों के लिए, यह समय तेजी से बढ़ा।

हमें तुरंत एहसास हुआ कि यह प्रक्रिया केवल कुछ स्वचालन के लिए भीख माँग रही थी।

न केवल हमें ऑपरेशन टीम के लिए खेद महसूस हुआ, जिन्हें सुबह-सुबह इस तरह के सांसारिक काम करने थे, लेकिन हम यह भी जानते थे कि जैसे-जैसे हमारे ऑर्डर की मात्रा बढ़ेगी, यह कार्य धीरे-धीरे मिशन असंभव हो जाएगा। हमने इसे एक अत्याधुनिक तकनीक विकसित करने के अवसर के रूप में देखा जो कि GOGOVAN के डेटा साइंस स्टैक का एक मुख्य घटक बन जाएगा।

हमने शुरुआत कैसे की?

हम बहुत क्लाइंट और ड्राइवर-केंद्रित हैं। नतीजतन, हम हमेशा अपने दृष्टिकोण से एक समस्या का विश्लेषण करने की कोशिश करते हैं ताकि यह समझ सकें कि हमारा समाधान उन्हें कैसे प्रभावित और लाभ पहुंचा सकता है। बहुत सारे विचार-मंथन के बाद, ये ऐसे लक्ष्य हैं जिनके साथ हम आए:

  • सभी आदेशों को समय पर पहुंचाने की आवश्यकता है।
  • सुनिश्चित करें कि ड्राइवरों को बफर समय और वास्तविक समय दूरी का उपयोग करके इसे समय पर बनाने के लिए जल्दी नहीं किया जाता है।
  • संचालित दूरी को कम करके ईंधन की बचत करें।
  • ड्राइवरों के लिए बेकार समय कम करें - कोई भी पैकेज से भरे ट्रंक के साथ इंतजार करना पसंद नहीं करता है।
  • वाहन उपयोग में सुधार।
  • पूरी तरह से स्वचालित प्रक्रिया।
  • एल्गोरिथ्म को हमारे साथ बढ़ने में सक्षम होना चाहिए - विभिन्न प्रकार के प्रसवों, वाहनों और देशों का समर्थन करना।

अपने मुख्य उद्देश्यों को निर्धारित करने के बाद, हमने शिक्षा की दुनिया और खुले स्रोत का पता लगाने का फैसला किया - पहिया को फिर से परिभाषित करने का कोई मतलब नहीं है। हमने महसूस किया कि जिस समस्या का हमें सामना करना पड़ा, उसे वाहन रूटिंग समस्या के रूप में व्यापक रूप से जाना गया।

वाहन रूटिंग समस्या क्या है?

वाहन रूटिंग समस्या (वीआरपी) को एक से एक इष्टतम मार्गों के सेट बनाने की समस्या के रूप में वर्णित किया जा सकता है, या कई, कई ग्राहकों को डिपो, बाधाओं के एक सेट के अधीन। इसका उद्देश्य सभी ग्राहकों को माल पहुंचाना है, साथ ही मार्गों की लागत और वाहनों की संख्या को कम से कम करना है।

यह समस्या एनपी-हार्ड है, जैसा कि लेनस्ट्रा और रिनॉयॉय कानो ने साबित किया है। हालांकि, अभी भी कुछ सटीक समाधान विधियां हैं, एक शाखा-और-बाउंड, या डायनेमिक प्रोग्रामिंग are का उपयोग करते हुए, हालांकि, जैसा कि ऊपर दिए गए कागजात में वर्णित है, वे केवल 150 वेपॉइंट तक काम करते प्रतीत होते हैं।

वर्तमान में, राज्य के अत्याधुनिक समाधान मेटाटैरिस्टिक्स का उपयोग करके प्राप्त किए जाते हैं: जेनेटिक एल्गोरिथम, टैबू सर्चो और एंट कॉलोनी ऑप्टिमाइज़ेशन। ये आजकल मुख्य रूप से क्षेत्र में उपयोग की जाने वाली विधियाँ हैं।

क्षेत्र की गहराई से समीक्षा के लिए, हम Xiaoyan Li द्वारा इस शानदार थीसिस की सलाह देते हैं।

हमारा समाधान

वीआरपी एक व्यापक रूप से मान्यता प्राप्त समस्या होने के साथ, वहाँ वास्तव में बहुत सी कंपनियां हैं जो इस समस्या से निपटने में लगती हैं।

हालाँकि, हम किसी भी तरह उनके समाधान से संतुष्ट नहीं थे ...

हमें सिर्फ इतना पता था कि अगर हमने अपने संचालन को जान लिया, डेटा साइंस और रिसर्च विशेषज्ञता, डेटा की बड़ी मात्रा और ओपन सोर्स अत्याधुनिक योगदान, तो हम एक मजबूत इन-हाउस समाधान पर पहुँच सकते हैं:

  • अधिक अद्यतित, प्रदर्शन करने वाला और अनुकूलन योग्य एल्गोरिदम और पुनरावृत्ति तर्क है।
  • सस्ता, अधिक कुशल और अधिक स्केलेबल है।
  • मूर्त बौद्धिक संपदा संपत्तियों को विकसित करने और इसके आसपास प्रतिस्पर्धी लाभ के निर्माण की अनुमति देता है।
  • हमें अपने ग्राहकों को यह गारंटी देने की अनुमति देता है कि उनका वितरण डेटा GOGOVAN से आगे नहीं जाएगा।

काफी समय तक इसके बारे में सोचने के बाद, हमने तय किया कि अगर हम क्षेत्र में अग्रणी बनना चाहते हैं, तो हमें इसे अपने तरीके से करने की आवश्यकता है, न कि कुछ ब्लैकबॉक्स समाधान का उपयोग करने की।

तो हम जा रहे हैं ...

पहला एल्गोरिथ्म

लेकिन हमने सीधे अकादमिक कागजात में गोता नहीं लगाया!

सबसे पहले, हमने अपने स्वयं के दृष्टिकोण के साथ आने और उनका मूल्यांकन करने पर ध्यान केंद्रित किया। इस प्रक्रिया ने हमें शुरुआत से ही क्षेत्र की बेहतर समझ प्राप्त करने और खुद के लिए कुछ सामान्य समस्याओं का अनुभव करने की अनुमति दी (हमने कुछ भी हासिल नहीं किया!)। क्या अधिक है, इससे हमें बाद में मदद मिली, क्योंकि हम अकादमिक पत्रों में प्रस्तुत किए गए विभिन्न तरीकों के पेशेवरों और विपक्षों को आसानी से देख सकते हैं और उन्हें संयोजित करने के लिए रणनीतियों के साथ आ सकते हैं।

इस तरह की प्रक्रिया सीधे समझने की कुंजी थी कि यह शानदार पैकेज - Google अनुकूलन उपकरण - कैसे काम करता है। हमने समझा कि Google के लोगों ने हमें महीनों बचाया कि हम उन सभी अलग-अलग एल्गोरिदम को कोडिंग में खर्च करेंगे, जिन्हें हम परीक्षण करना चाहते थे। उन्होंने हमें तुरंत सबसे दिलचस्प भाग में उतरने की अनुमति दी!

हमने उस लाइब्रेरी के साथ खेलने, विभिन्न परिदृश्यों का परीक्षण करने और खुद को देखने के लिए बहुत समय बिताया कि कौन सी रणनीतियों ने कब काम किया।

हमें यह बहुत पसंद आया, हमने इसके चारों ओर अपना टूल बनाने का फैसला किया!

यह हमारे लिए आवश्यक था - पारदर्शिता, प्रयोग करने की क्षमता, लचीलापन और समर्थन।

पहले एल्गोरिथ्म तैयार था। हमने इसे तैनात किया।

चित्र 1: हमारे पहले रूट अनुकूलन कार्यों में से एक का विज़ुअलाइज़ेशन

तेजी से विकास - अधिक ऑर्डर कैसे संभालें?

रूट ऑप्टिमाइज़ेशन का पहला संस्करण एक बड़ी सफलता निकला।

रूट ऑप्टिमाइज़र को सबमिट किए गए आदेशों की मात्रा 500 आइटम प्रति गोदाम से 1000+ तक बढ़ गई। सैद्धांतिक रूप से, हमें ठीक होना चाहिए।

लेकिन हम नहीं थे।

1 मिनट और 500 एमबी से 10 मिनट और 5 जीबी तक - हमारे एल्गोरिथ्म रनटाइम्स और मेमोरी उपयोग अविश्वसनीय रूप से जल्दी से कूद गए। जैसा कि हमने उच्च और उच्च संस्करणों के लिए इसका परीक्षण किया, हम अंत में अधिकतम पहुंच गए - 2000 के तरीके के लिए मॉड्यूल 25 जीबी रैम मेमोरी का उपयोग करता है।

यह अस्वीकार्य था।

असल में, हमारे पास दो विकल्प थे:

  • एक बिल्कुल नया रूट ऑप्टिमाइज़र बनाएँ जो डिफ़ॉल्ट रूप से इस तरह के बड़े संस्करणों का समर्थन करने में सक्षम होगा
  • एक नया एल्गोरिथ्म बनाएं जो वर्तमान कार्यान्वयन के शीर्ष पर चलेगा - शायद एक विधि जो छोटे बैचों में आदेशों को संयोजित करेगी जो तब मुख्य अनुकूलन एल्गोरिदम को प्रस्तुत की जाएगी।

जैसा कि हम व्यावहारिक हैं (और हमारे द्वारा पहले से किए गए महान काम के शीर्ष पर भी प्रेम निर्माण), हमने दूसरे विकल्प के साथ आगे बढ़ने का फैसला किया।

हम छोटे बैच कैसे बनाते हैं?

आइए एक वृहत क्लस्टरिंग एल्गोरिदम के साथ शुरू करें - DBSCAN ren।

हमारे पास एक अत्याधुनिक तरीका है जो भौगोलिक बिंदुओं को एक साथ समूहित करता है। हालांकि, इसका नकारात्मक पक्ष यह है: प्रत्येक क्लस्टर में एक ही त्रिज्या होना चाहिए।

यह वह नहीं है जो हम एक साधारण कारण के लिए चाहते हैं: त्सिम शा त्सि में 1 किमी त्रिज्या के एक क्लस्टर में 1000 ऑर्डर हो सकते हैं, जबकि पोक फू लाम और वाटरफॉल बे में अन्य 1 किमी क्लस्टर में प्रत्येक में केवल 3 ऑर्डर हो सकते हैं।

ये क्लस्टर वास्तव में अक्षम और असमान होंगे ...

Tsim Sha Tsui में, क्लस्टर का आकार बहुत बड़ा होगा - हमारे पास एक क्लस्टर में बहुत अधिक ऑर्डर होंगे। लेकिन एक ही समय में, कुछ अन्य क्षेत्रों में यह त्रिज्या पर्याप्त नहीं होगी - क्लस्टर बहुत छोटे होंगे और जो ऑर्डर अपेक्षाकृत करीब एक साथ होंगे वे अलग-अलग समूहों में होंगे।

यही कारण है कि हमने एक संशोधित दृष्टिकोण का उपयोग करने का फैसला किया - जिसे "पुनरावर्ती-डीबीएससीएएन" कहा जाता है।

पुनरावर्ती-DBSCAN

यह DBSCAN की चमक पर बनाता है, लेकिन एक ही समय में हमें उच्च मार्ग-घनत्व क्षेत्रों में गहराई से खुदाई करने की अनुमति देता है, जबकि दूरस्थ आदेशों को एक साथ समूहित करता है।

आदेशों की एक सूची के लिए, हम त्रिज्या का पता लगाना चाहते हैं, जिसके लिए वेपाइंट्स की औसत संख्या सबसे बड़ी होगी (लेकिन क्लस्टर की संख्या min_no_clusters से अधिक होगी)। हम एक साधारण द्विआधारी खोज एल्गोरिथ्म का उपयोग करके ऐसा करते हैं।

एक बार जब हम इष्टतम समाधान पा लेते हैं, तो हम क्लस्टर में "प्रवेश" करते हैं जो बहुत बड़ा होता है और एक ही तर्क को लागू करता है जब तक कि हम एक बिंदु तक नहीं पहुंचते जब प्रत्येक क्लस्टर में max_len_cluster से कम होता है।

फिर, प्रत्येक क्लस्टर के लिए, हम Google ऑप्टिमाइज़ेशन टूल का उपयोग करके रूट ऑप्टिमाइज़ेशन एल्गोरिथ्म चलाते हैं। उम्मीद है, यह हमें एक समान परिणाम अधिक तेज़ी से देगा, और कम रैम मेमोरी का उपयोग करेगा।

छद्म कोड निम्नानुसार है:

मानक

हम बहुत उत्सुक थे कि हमारा तरीका कैसा प्रदर्शन करेगा, लेकिन साथ ही हम चिंतित थे कि पुनरावृत्ति बहुत लंबे समय तक चल सकती है, फलस्वरूप हमारे एल्गोरिथ्म को आधार रेखा विधि से बेहतर नहीं बनाया जा सकता है।

इसीलिए हमने सबसे पहले रनटाइम्स पर एक नज़र डालने का फैसला किया:

यह पता चला कि पुनरावर्ती-डीबीएसकेएन एल्गोरिथ्म ने Google अनुकूलन उपकरण विधि को बहुत बेहतर बना दिया। उसी समय यह डबस्कैन विधि के रनटाइम्स से बहुत अलग नहीं था।

हम केवल RAM आदेश उपयोग समस्या के कारण अधिकतम 2000 आदेशों और Google ऑप्टिमाइज़ेशन टूल 1500 आदेशों के लिए dbscan चलाने में सक्षम थे: मेमोरी आवश्यक होने पर दोनों विधियाँ 25 GB से अधिक हो गई थीं।

रनटाइम्स महत्वपूर्ण हैं, लेकिन जिस चीज पर हमारी दिलचस्पी थी, वह यह है कि बेसलाइन विधि की तुलना में हमारा नया एल्गोरिदम कुल दूरी और प्रयुक्त वाहनों की संख्या के संदर्भ में कैसा प्रदर्शन करता है। ये दो रेखांकन बताते हैं कि:

जैसा कि हम देखते हैं, पुनरावर्ती विधि दोनों दूरी और वाहनों की संख्या के संदर्भ में Google अनुकूलन उपकरण विधि का बारीकी से अनुसरण करती है। एक ही समय में, यह dbscan विधि outperforms।

इसका मतलब है कि हमारा नया एल्गोरिथ्म बेसलाइन की तुलना में तेज है और इसमें पाए जाने वाले समाधान की गुणवत्ता उतनी ही अच्छी है। इसके अलावा, अधिकतम रैम का उपयोग "केवल" 1GB है!

समझ गए!

DBSCAN बनाम पुनरावर्ती-DBSCAN

हम आपको यह भी दिखाना चाहते थे कि दूरस्थ तरीके के लिए कैसे पुनरावर्ती-डीबीएसकेन बेहतर तरीके से काम करता है।

चित्र 5: ओड DBSCAN और पुनरावर्ती-DBSCAN मार्गों की तुलना करें। हम जानते हैं कि वे अभी भी परिपूर्ण नहीं हैं!

ऊपर, बाईं ओर हमारे पास एक नक्शा है जो सामान्य DBSCAN एल्गोरिथ्म का उपयोग करते हुए एक असाइनमेंट दिखा रहा है। हम देख सकते हैं कि कई ड्राइवर केवल एक ही ऑर्डर देते हैं - क्योंकि ये ऑर्डर उनके बैच में ही होते हैं।

दाईं ओर हम देखते हैं कि पुनरावर्ती विधि इस मुद्दे को काफी अच्छी तरह से संभालती है, विभिन्न क्षेत्रों के लिए अलग-अलग राडियों का उपयोग करके, यह एक समाधान खोजने का प्रबंधन करता है जो केवल 3 वाहनों का उपयोग करके सभी ऑर्डर बचाता है!

यह एक आदर्श दृश्य है कि हमारे उपयोग के मामले के लिए पुनरावर्ती-डीबीएसकेन विधि कैसे बेहतर है और हमने इसका उपयोग करने के लिए क्यों चुना।

निष्कर्ष (उर्फ टीएल; डीआर)

इस लेख में, हमने बड़ी संख्या में वेपॉइंट्स (5000 तक) के लिए टाइम विंडोज के साथ कैपेसिटिव व्हीकल रूटिंग प्रॉब्लम के लिए अपना दृष्टिकोण प्रस्तुत किया है। एक पुनरावर्ती-डीबीएसकेन विधि का उपयोग करके हम आधार रेखा Google अनुकूलन उपकरण विधि के समान परिणामों की गुणवत्ता बनाए रखते हुए, रनटाइम और मेमोरी उपयोग को कम करने में सक्षम थे।

यह एल्गोरिथ्म हमारी संचालन टीम के लिए बहुत मददगार है, सीपीयू समय के कुछ मिनटों में सांसारिक मैनुअल काम के घंटों को कम करता है (और एक मानव द्वारा परिणामों की दोहरी जांच)।

भविष्य

हम जानते हैं कि हमारा उपकरण सही नहीं है।

मुख्य समस्याओं में से एक यह है कि यह अभी भी एक स्थिर विधि है, कि अगर एक बार बेहतर मार्ग उपलब्ध हो जाता है, या यदि सड़क की स्थिति बदलती है, तो एक बार चलाने के लिए खुद को अपडेट नहीं किया जाएगा। इस मामले में हमारे पास कुछ विकल्प हैं, एक तो लाइफ़ की तरह जियोशिंग लागू करना, या कोई दूसरा जो हमारे सहयोगी से आ रहा है-पॉलीयू हांगकांग में बिग डेटा एनालिटिक्स में खोज सुविधा।

हमारा लक्ष्य रूट ऑप्टिमाइज़ेशन में सुधार करना है ताकि यह लगातार ड्राइवरों पर नज़र रखे और अलर्ट भेजे अगर ड्राइवरों को कुछ पार्सल के साथ इसे समय पर नहीं बनाने का खतरा है - यह सब हमारे ग्राहकों को हमारी सेवा के साथ खुश करने के लिए।

उम्मीद है, इस लेख ने आपको उन समस्याओं के बारे में कुछ अच्छी जानकारी प्रदान की है जो हम GOGOVAN से निपटते हैं। यदि यह आपको रुचिकर लगता है, या आप अधिक जानने में रुचि रखते हैं, तो कृपया संपर्क करने में संकोच न करें।

भविष्य के सुधार के लिए स्वाभाविक रूप से बहुत कुछ है, लेकिन हम अपने कुछ दृष्टिकोणों को साझा करने की उम्मीद करते हैं ताकि चर्चा और मांग रसद कार्यों के अनुकूलन के आकर्षक क्षेत्र में प्रगति हो सके।
यदि आप हमारी डेटा टीम के बारे में अधिक जानकारी प्राप्त करना चाहते हैं, तो कृपया हमारे प्रमुख के डेटा लेख को यहाँ देखें।
हम हमेशा शीर्ष एप्लाइड ऑपरेशंस और एमएल रिसर्च प्रतिभा की तलाश में हैं। कृपया संपर्क करें यदि रुचि हो! (ऑनसाइट और रिमोट)
संदर्भ:
[१] लेनस्ट्रा, जे। के। और कान, ए। एच। (१ ९ ra१), वाहन रूटिंग और शेड्यूलिंग समस्याओं की जटिलता। नेटवर्क, 11: 221–227। doi: 10.1002 / net.3230110211
[२] फुकसावा, आर।, लोंगो, एच।, लिसगार्ड, जे। एट अल। गणित। कार्यक्रम। (2006) 106: 491।
[३] बाल्डशेक, आर। एंड मिंगोजी, ए। मठ। कार्यक्रम। (2009) 120: 347. https://doi.org/10.1007/s10107-008-0218-9
[४] नगाता वाई। (२०० 2007) एज असेंबली क्रॉसओवर फॉर द कैपसिटेटेड व्हीकल रूटिंग प्रॉब्लम। में: Cotta सी, वैन हेमर्ट जे। (Eds) कंबाइनटोरियल ऑप्टिमाइज़ेशन में इवोल्यूशनरी कम्प्यूटेशन। EvoCOP 2007. लेक्चर नोट्स इन कंप्यूटर साइंस, वॉल्यूम 4446। स्प्रिंगर, बर्लिन, हीडलबर्ग
[५] ब्रायसी, ओ। एंड गेंड्रेयू, एम। टॉप (२००२) १०: २११। https://doi.org/10.1007/BF02579017
[६] टैन एक्स।, झोउ एक्स।, झांग जे। (२००६) चींटी कॉलोनी सिस्टम फॉर ऑप्टिमाइज़िंग व्हीकल रूटिंग प्रॉब्लम विथ टाइम विंडोज (वीआरपीटीडब्ल्यू)। में: हुआंग डी.एस., ली के।, इरविन जी.डब्ल्यू। (eds) कम्प्यूटेशनल इंटेलिजेंस एंड बायोइनफॉरमैटिक्स। ICIC 2006. कंप्यूटर विज्ञान में व्याख्यान नोट्स, वॉल्यूम 4115। स्प्रिंगर, बर्लिन, हीडलबर्ग
[[] Xiaoyan Li (२०१५) समय के साथ समाप्‍त वाहन रूटिंग की समस्‍या
[[] एम। एस्टर, एच। क्रिएगेल, जे। सैंडर और एक्स। जू, "प्रोक में शोर के साथ बड़े स्थानिक डेटाबेस में क्लस्टर की खोज के लिए घनत्व-आधारित एल्गोरिथ्म,"। दूसरा इंट। सम्मेलन। नॉलेज डिस्कवरी एंड डेटा माइनिंग (KDD’96), 1996, पीपी। 226231