কিভাবে Yandex.Taxi গাড়ির জন্য অনুসন্ধান করে যখন কোনটি নেই

একটি ভাল ট্যাক্সি পরিষেবা নিরাপদ, নির্ভরযোগ্য এবং দ্রুত হওয়া উচিত। ব্যবহারকারী বিশদ বিবরণে যাবেন না: এটি তার জন্য গুরুত্বপূর্ণ যে তিনি "অর্ডার" বোতামটি ক্লিক করেন এবং যত তাড়াতাড়ি সম্ভব একটি গাড়ি গ্রহণ করেন যা তাকে পয়েন্ট A থেকে বি পয়েন্টে নিয়ে যাবে৷ যদি কাছাকাছি কোনও গাড়ি না থাকে তবে পরিষেবাটি উচিত অবিলম্বে এই সম্পর্কে অবহিত যাতে ক্লায়েন্ট মিথ্যা প্রত্যাশা ছিল না. তবে যদি "কোন গাড়ি নেই" চিহ্নটি প্রায়শই প্রদর্শিত হয়, তবে এটি যৌক্তিক যে একজন ব্যক্তি কেবল এই পরিষেবাটি ব্যবহার করা বন্ধ করবেন এবং প্রতিযোগীর কাছে যাবেন।

এই নিবন্ধে আমি কীভাবে, মেশিন লার্নিং ব্যবহার করে, আমরা কম ঘনত্বের এলাকায় (অন্য কথায়, যেখানে প্রথম নজরে, কোনও গাড়ি নেই) গাড়ির সন্ধানের সমস্যা সমাধান করেছি সে সম্পর্কে কথা বলতে চাই। এবং এটা কি এসেছে.

প্রাগঐতিহাসিক

একটি ট্যাক্সি কল করার জন্য, ব্যবহারকারী কয়েকটি সহজ পদক্ষেপ সঞ্চালন করে, কিন্তু পরিষেবার ভিতরে কী ঘটে?

ব্যবহারকারী	পর্যায়	ব্যাকএন্ড Yandex.Taxi
প্রারম্ভিক বিন্দু নির্বাচন করে	পিন	আমরা প্রার্থীদের জন্য একটি সরলীকৃত অনুসন্ধান চালু করছি - পিন অনুসন্ধান। পাওয়া ড্রাইভারের উপর ভিত্তি করে, আগমনের সময় পূর্বাভাস দেওয়া হয় - পিনে ETA। একটি নির্দিষ্ট বিন্দুতে ক্রমবর্ধমান সহগ গণনা করা হয়।
গন্তব্য, ভাড়া, প্রয়োজনীয়তা নির্বাচন করে	অফার	আমরা একটি রুট তৈরি করি এবং ক্রমবর্ধমান সহগকে বিবেচনায় রেখে সমস্ত ট্যারিফের জন্য মূল্য গণনা করি।
"ট্যাক্সি কল করুন" বোতাম টিপুন	ক্রম	আমরা গাড়ির জন্য একটি সম্পূর্ণ অনুসন্ধান চালু. আমরা সবচেয়ে উপযুক্ত ড্রাইভার নির্বাচন করি এবং তাকে একটি অর্ডার অফার করি।

উপর পিনে ETA, মূল্য গণনা и সবচেয়ে উপযুক্ত ড্রাইভার নির্বাচন করা আমরা ইতিমধ্যে লিখেছি। এবং এটি ড্রাইভার খোঁজার একটি গল্প। যখন একটি অর্ডার তৈরি করা হয়, অনুসন্ধানটি দুইবার হয়: পিনে এবং অর্ডারে। একটি আদেশের জন্য অনুসন্ধান দুটি পর্যায়ে সঞ্চালিত হয়: প্রার্থীদের নিয়োগ এবং র্যাঙ্কিং। প্রথমত, উপলভ্য প্রার্থী চালকদের খুঁজে পাওয়া যায় যারা রাস্তার গ্রাফ বরাবর সবচেয়ে কাছাকাছি। তারপর বোনাস এবং ফিল্টারিং প্রয়োগ করা হয়। অবশিষ্ট প্রার্থীদের র‌্যাঙ্ক করা হয় এবং বিজয়ী একটি অর্ডার অফার পায়। যদি সে সম্মত হয়, তাকে অর্ডারের জন্য বরাদ্দ করা হয় এবং ডেলিভারি পয়েন্টে যায়। যদি তিনি প্রত্যাখ্যান করেন, তবে অফারটি পরেরটির কাছে আসে। আর কোন প্রার্থী না থাকলে, আবার অনুসন্ধান শুরু হয়। এটি তিন মিনিটের বেশি স্থায়ী হয় না, তারপরে অর্ডারটি বাতিল এবং বার্ন করা হয়।

একটি পিনে অনুসন্ধান করা একটি অর্ডার অনুসন্ধানের অনুরূপ, শুধুমাত্র অর্ডার তৈরি করা হয় না এবং অনুসন্ধানটি শুধুমাত্র একবারই সঞ্চালিত হয়। প্রার্থীদের সংখ্যা এবং অনুসন্ধান ব্যাসার্ধের জন্য সরলীকৃত সেটিংসও ব্যবহার করা হয়। এই ধরনের সরলীকরণ প্রয়োজনীয় কারণ অর্ডারের চেয়ে বেশি পিনের ক্রম রয়েছে এবং অনুসন্ধান করা একটি বরং কঠিন অপারেশন। আমাদের গল্পের মূল বিষয়: প্রাথমিক অনুসন্ধানের সময় যদি পিনে উপযুক্ত প্রার্থী না পাওয়া যায়, তাহলে আমরা আপনাকে অর্ডার দেওয়ার অনুমতি দিই না। অন্ততঃ এমনই হতো।

ব্যবহারকারী অ্যাপ্লিকেশনটিতে এটি দেখেছেন:

গাড়ি ছাড়া গাড়ির জন্য অনুসন্ধান করুন

একদিন আমরা একটি অনুমান নিয়ে এসেছি: সম্ভবত কিছু ক্ষেত্রে অর্ডারটি এখনও সম্পূর্ণ করা যেতে পারে, এমনকি পিনে কোনও গাড়ি না থাকলেও। সর্বোপরি, পিন এবং অর্ডারের মধ্যে কিছু সময় চলে যায় এবং অর্ডারের অনুসন্ধান আরও সম্পূর্ণ হয় এবং কখনও কখনও বেশ কয়েকবার পুনরাবৃত্তি হয়: এই সময়ের মধ্যে, উপলব্ধ ড্রাইভার উপস্থিত হতে পারে। আমরা উল্টোটাও জানতাম: যদি চালকদের পিনে পাওয়া যায়, তবে অর্ডার দেওয়ার সময় তাদের পাওয়া যাবে এমন কোনো তথ্য ছিল না। কখনও কখনও তারা অদৃশ্য হয়ে যায় বা সবাই আদেশ প্রত্যাখ্যান করে।

এই হাইপোথিসিসটি পরীক্ষা করার জন্য, আমরা একটি পরীক্ষা শুরু করেছি: আমরা ব্যবহারকারীদের একটি পরীক্ষা গোষ্ঠীর জন্য একটি পিনে অনুসন্ধানের সময় গাড়ির উপস্থিতি পরীক্ষা করা বন্ধ করে দিয়েছি, অর্থাৎ, তাদের "গাড়ি ছাড়া অর্ডার" করার সুযোগ ছিল। ফলাফলটি বেশ অপ্রত্যাশিত ছিল: যদি গাড়িটি পিনে না থাকে, তবে 29% ক্ষেত্রে এটি পরে পাওয়া গেছে - অর্ডারে অনুসন্ধান করার সময়! তদুপরি, গাড়ি ছাড়া অর্ডারগুলি বাতিলকরণের হার, রেটিং এবং অন্যান্য গুণমান সূচকের ক্ষেত্রে নিয়মিত অর্ডারগুলির থেকে উল্লেখযোগ্যভাবে আলাদা ছিল না। গাড়ি ছাড়া বুকিং সমস্ত বুকিংয়ের 5%, কিন্তু সমস্ত সফল ভ্রমণের মাত্র 1% এর বেশি।

এই আদেশের নির্বাহক কোথা থেকে এসেছে তা বোঝার জন্য, আসুন একটি পিনে অনুসন্ধানের সময় তাদের স্থিতি দেখি:

• উপলব্ধ: উপলব্ধ ছিল, কিন্তু কিছু কারণে প্রার্থীদের অন্তর্ভুক্ত করা হয়নি, উদাহরণস্বরূপ, তিনি অনেক দূরে ছিলেন;
• আদেশ: ব্যস্ত ছিল, কিন্তু নিজেকে মুক্ত করতে বা জন্য উপলব্ধ হতে পরিচালিত চেইন অর্ডার;
• ব্যস্ত: আদেশ গ্রহণ করার ক্ষমতা অক্ষম ছিল, কিন্তু তারপর ড্রাইভার লাইনে ফিরে আসেন;
• পাওয়া যায় না: ড্রাইভার অনলাইন ছিল না, কিন্তু তিনি হাজির.

এর নির্ভরযোগ্যতা যোগ করা যাক

অতিরিক্ত অর্ডারগুলি দুর্দান্ত, তবে 29% সফল অনুসন্ধানের অর্থ হল 71% সময় ব্যবহারকারী দীর্ঘ সময় অপেক্ষা করেছেন এবং শেষ পর্যন্ত কোথাও যাননি৷ যদিও এটি সিস্টেমের দক্ষতার দৃষ্টিকোণ থেকে একটি খারাপ জিনিস নয়, এটি আসলে ব্যবহারকারীকে মিথ্যা আশা দেয় এবং সময় নষ্ট করে, যার পরে তারা বিরক্ত হয় এবং (সম্ভবত) পরিষেবাটি ব্যবহার করা বন্ধ করে দেয়। এই সমস্যাটি সমাধান করার জন্য, আমরা অর্ডারে একটি গাড়ি পাওয়া যাওয়ার সম্ভাবনার ভবিষ্যদ্বাণী করতে শিখেছি।

স্কিমটি নিম্নরূপ:

• ব্যবহারকারী একটি পিন রাখে।
• একটি অনুসন্ধান পিন উপর বাহিত হয়.
• যদি কোনও গাড়ি না থাকে, আমরা ভবিষ্যদ্বাণী করি: সম্ভবত তারা উপস্থিত হবে।
• এবং সম্ভাব্যতার উপর নির্ভর করে, আমরা আপনাকে অর্ডার দেওয়ার অনুমতি দিই বা না, তবে আমরা আপনাকে সতর্ক করি যে এই সময়ে এই এলাকায় গাড়ির ঘনত্ব কম।

অ্যাপ্লিকেশনে এটি এই মত দেখায়:

মডেল ব্যবহার করে আপনি আরও সঠিকভাবে নতুন অর্ডার তৈরি করতে পারবেন এবং নিরর্থক লোকেদের আশ্বস্ত করবেন না। অর্থাৎ, নির্ভুলতা-রিকল মডেল ব্যবহার করে মেশিন ছাড়াই নির্ভরযোগ্যতার অনুপাত এবং অর্ডারের সংখ্যা নিয়ন্ত্রণ করা। পরিষেবার নির্ভরযোগ্যতা পণ্যটি ব্যবহার চালিয়ে যাওয়ার ইচ্ছাকে প্রভাবিত করে, অর্থাৎ শেষ পর্যন্ত এটি সমস্ত ভ্রমণের সংখ্যায় নেমে আসে।

নির্ভুলতা সম্পর্কে একটু-প্রত্যাহারমেশিন লার্নিংয়ের একটি মৌলিক কাজ হল শ্রেণীবিভাগের কাজ: দুটি শ্রেণীর একটিতে একটি বস্তু বরাদ্দ করা। এই ক্ষেত্রে, মেশিন লার্নিং অ্যালগরিদমের ফলাফল প্রায়শই ক্লাসগুলির একটিতে সদস্যতার সংখ্যাসূচক মূল্যায়ন হয়ে ওঠে, উদাহরণস্বরূপ, একটি সম্ভাব্যতা মূল্যায়ন। যাইহোক, সঞ্চালিত ক্রিয়াগুলি সাধারণত বাইনারি হয়: যদি গাড়িটি উপলব্ধ থাকে, তাহলে আমরা আপনাকে এটি অর্ডার করতে দেব, এবং যদি না হয়, তাহলে আমরা তা করব না। সুনির্দিষ্ট হওয়ার জন্য, আসুন একটি অ্যালগরিদম বলি যা একটি সংখ্যাগত অনুমান একটি মডেল তৈরি করে এবং একটি শ্রেণিবদ্ধকারী একটি নিয়ম যা এটিকে দুটি শ্রেণির (1 বা –1) মধ্যে একটিকে বরাদ্দ করে। মডেল মূল্যায়নের উপর ভিত্তি করে একটি শ্রেণীবিভাগ তৈরি করতে, আপনাকে একটি মূল্যায়ন থ্রেশহোল্ড নির্বাচন করতে হবে। ঠিক কিভাবে টাস্ক উপর ব্যাপকভাবে নির্ভর করে.

ধরুন আমরা কিছু বিরল এবং বিপজ্জনক রোগের জন্য একটি পরীক্ষা (ক্ল্যাসিফায়ার) করছি। পরীক্ষার ফলাফলের উপর ভিত্তি করে, আমরা হয় রোগীকে আরও বিশদ পরীক্ষার জন্য পাঠাই, অথবা বলি: "ভাল, বাড়িতে যান।" আমাদের জন্য, একজন অসুস্থ ব্যক্তিকে বাড়িতে পাঠানো একজন সুস্থ ব্যক্তির অযথা পরীক্ষা করার চেয়ে অনেক খারাপ। অর্থাৎ, আমরা চাই যে পরীক্ষাটি যতটা সম্ভব অসুস্থ মানুষের জন্য কাজ করুক। এই মানটিকে recall = বলা হয়. একটি আদর্শ শ্রেণীবদ্ধকারীর 100% রিকল থাকে। একটি অধঃপতন পরিস্থিতি হল সবাইকে পরীক্ষার জন্য পাঠাতে হবে, তাহলে রিকলও 100% হবে।

এটি প্রায় উল্টোটাও ঘটে। উদাহরণস্বরূপ, আমরা শিক্ষার্থীদের জন্য একটি পরীক্ষার ব্যবস্থা করছি এবং এতে একটি প্রতারণা সনাক্তকারী রয়েছে৷ যদি হঠাৎ করে চেকটি প্রতারণার কিছু ক্ষেত্রে কাজ না করে, তবে এটি অপ্রীতিকর, তবে সমালোচনামূলক নয়। অন্যদিকে, ছাত্ররা যা করেনি তার জন্য অন্যায়ভাবে অভিযুক্ত করা অত্যন্ত খারাপ। অর্থাৎ, এটি আমাদের জন্য গুরুত্বপূর্ণ যে শ্রেণিবিন্যাসকারীর ইতিবাচক উত্তরগুলির মধ্যে যতটা সম্ভব সঠিক উত্তর রয়েছে, সম্ভবত তাদের সংখ্যার ক্ষতির জন্য। এর মানে হল যে আপনাকে সর্বোচ্চ নির্ভুলতা = . যদি সমস্ত বস্তুতে ট্রিগারিং ঘটে, তাহলে নির্ভুলতা নমুনায় সংজ্ঞায়িত শ্রেণীর ফ্রিকোয়েন্সির সমান হবে।

যদি অ্যালগরিদম একটি সাংখ্যিক সম্ভাব্যতার মান তৈরি করে, তাহলে বিভিন্ন থ্রেশহোল্ড নির্বাচন করে, আপনি বিভিন্ন নির্ভুলতা-রিকল মান অর্জন করতে পারেন।

আমাদের সমস্যায় পরিস্থিতি নিম্নরূপ। প্রত্যাহার আমরা অফার করতে পারেন অর্ডার সংখ্যা, নির্ভুলতা এই আদেশ নির্ভরযোগ্যতা. আমাদের মডেলের নির্ভুলতা-রিকল বক্ররেখা এইরকম দেখায়:

দুটি চরম কেস আছে: কাউকে অর্ডার করতে দেবেন না এবং সবাইকে অর্ডার করতে দেবেন না। আপনি যদি কাউকে অনুমতি না দেন, তাহলে প্রত্যাহার 0 হবে: আমরা অর্ডার তৈরি করি না, তবে তাদের কেউই ব্যর্থ হবে না। আমরা যদি সবাইকে অনুমতি দিই, তাহলে প্রত্যাহার হবে 100% (আমরা সমস্ত সম্ভাব্য অর্ডার পাব), এবং যথার্থতা 29% হবে, অর্থাৎ 71% অর্ডার খারাপ হবে।

আমরা লক্ষণ হিসাবে প্রারম্ভিক বিন্দুর বিভিন্ন পরামিতি ব্যবহার করেছি:

• সময়/স্থান।
• সিস্টেমের অবস্থা (আশেপাশে সমস্ত ট্যারিফ এবং পিনের দখলকৃত মেশিনের সংখ্যা)।
• অনুসন্ধান পরামিতি (ব্যাসার্ধ, প্রার্থীর সংখ্যা, সীমাবদ্ধতা)।

লক্ষণ সম্পর্কে আরো

ধারণাগতভাবে, আমরা দুটি পরিস্থিতির মধ্যে পার্থক্য করতে চাই:

• "গভীর বন" - এই সময়ে এখানে কোন গাড়ি নেই।
• "দুর্ভাগ্য" - গাড়ি আছে, কিন্তু অনুসন্ধান করার সময় কোন উপযুক্ত ছিল না।

শুক্রবার সন্ধ্যায় কেন্দ্রে প্রচুর চাহিদা থাকলে "দুর্ভাগ্য" এর একটি উদাহরণ। অনেক অর্ডার আছে, অনেক লোক ইচ্ছুক, এবং প্রত্যেকের জন্য পর্যাপ্ত ড্রাইভার নেই। এটি এই মত চালু হতে পারে: পিনে কোন উপযুক্ত ড্রাইভার নেই। কিন্তু আক্ষরিক অর্থে সেকেন্ডের মধ্যে তারা উপস্থিত হয়, কারণ এই সময়ে এই জায়গায় প্রচুর ড্রাইভার রয়েছে এবং তাদের অবস্থা ক্রমাগত পরিবর্তিত হচ্ছে।

অতএব, পয়েন্ট A এর আশেপাশে বিভিন্ন সিস্টেম সূচকগুলি ভাল বৈশিষ্ট্য হিসাবে প্রমাণিত হয়েছে:

• মোট গাড়ির সংখ্যা।
• অর্ডারে গাড়ির সংখ্যা।
• "ব্যস্ত" অবস্থায় অর্ডার করার জন্য অনুপলব্ধ গাড়ির সংখ্যা।
• ব্যবহারকারীর সংখ্যা.

সর্বোপরি, যত বেশি গাড়ি রয়েছে, তাদের মধ্যে একটি উপলব্ধ হওয়ার সম্ভাবনা তত বেশি।
আসলে, এটি আমাদের জন্য গুরুত্বপূর্ণ যে কেবল গাড়িগুলিই অবস্থিত নয়, সফল ভ্রমণও করা হয়। অতএব, এটি একটি সফল ট্রিপ সম্ভাবনা ভবিষ্যদ্বাণী করা সম্ভব ছিল. তবে আমরা এটি না করার সিদ্ধান্ত নিয়েছি, কারণ এই মানটি ব্যবহারকারী এবং ড্রাইভারের উপর নির্ভর করে।

মডেল প্রশিক্ষণ অ্যালগরিদম ছিল ক্যাটবুস্ট. পরীক্ষা থেকে প্রাপ্ত ডেটা প্রশিক্ষণের জন্য ব্যবহার করা হয়েছিল। বাস্তবায়নের পরে, প্রশিক্ষণের ডেটা সংগ্রহ করতে হয়েছিল, কখনও কখনও অল্প সংখ্যক ব্যবহারকারীকে মডেলের সিদ্ধান্তের বিরুদ্ধে অর্ডার দেওয়ার অনুমতি দেয়।

ফলাফল

পরীক্ষার ফলাফলগুলি প্রত্যাশিত ছিল: মডেল ব্যবহার করে আপনি গাড়ি ছাড়াই অর্ডারের কারণে সফল ভ্রমণের সংখ্যা উল্লেখযোগ্যভাবে বৃদ্ধি করতে পারবেন, তবে নির্ভরযোগ্যতার সাথে আপস না করে।

এই মুহুর্তে, প্রক্রিয়াটি সমস্ত শহর এবং দেশে চালু করা হয়েছে এবং এর সাহায্যে প্রায় 1% সফল ভ্রমণ ঘটে। তদুপরি, গাড়ির কম ঘনত্ব সহ কিছু শহরে, এই জাতীয় ভ্রমণের ভাগ 15% পৌঁছেছে।

ট্যাক্সি প্রযুক্তি সম্পর্কে অন্যান্য পোস্ট

• কিভাবে আমরা Yandex.Taxi-এ ড্রাইভারদের মধ্যে অর্ডার বিতরণ করি
• গতিশীল মূল্য, বা কিভাবে Yandex.Taxi উচ্চ চাহিদার পূর্বাভাস দেয়
• একটি গাড়ির অবস্থা মূল্যায়ন করতে কম্পিউটার দৃষ্টি কিভাবে ব্যবহার করবেন। Yandex.Taxi অভিজ্ঞতা
• কিভাবে Yandex.Taxi মেশিন লার্নিং ব্যবহার করে গাড়ি পিক-আপের সময়ের পূর্বাভাস দেয়

উত্স: www.habr.com