اشتراکگذاری دوچرخه شناور آزاد: حل مشکلات واقعی تعادل استاتیک در مقیاس بزرگ ☆

اشتراک دوچرخه شناور آزاد (FFBS) یک مدل نوآورانه اشتراک دوچرخه است. FFBS با اجتناب از ساخت ایستگاه های گران قیمت و ماشین آلات کیوسک، در هزینه راه اندازی، در مقایسه با اشتراک دوچرخه مبتنی بر ایستگاه (SBBS) صرفه جویی می کند. FFBS از سرقت دوچرخه جلوگیری می کند و فرصت های قابل توجهی برای مدیریت هوشمند با ردیابی دوچرخه ها در زمان واقعی با GPS داخلی ارائه می دهد. با این حال، مانند SBBS، موفقیت FFBS به کارایی عملیات تعادل مجدد آن برای تامین حداکثر تقاضای ممکن بستگی دارد.

تعادل مجدد دوچرخه به برقراری مجدد تعداد دوچرخه ها در سایت ها به مقدار دلخواه با استفاده از ناوگان وسایل نقلیه حمل دوچرخه اشاره دارد. تعادل مجدد استاتیک برای SBBS یک مسئله بهینه سازی ترکیبی چالش برانگیز است. FFBS با افزایش مقیاس مشکل، آن را یک گام فراتر می برد. این مقاله اولین تلاش در یک سری از مطالعات برنامه ریزی و مدیریت FFBS است که به تعادل مجدد استاتیک با وسایل نقلیه تک و چندگانه پرداخته است. ما یک برنامه خطی عدد صحیح مختلط جدید را برای حل مسئله تعادل کامل استاتیکی ارائه می دهیم. فرمول پیشنهادی، نه تنها می تواند تک و چند وسیله نقلیه را مدیریت کند، بلکه امکان بازدیدهای متعدد از یک گره توسط یک وسیله نقلیه را نیز فراهم می کند. ما یک جستجوی محله بزرگ تو در تو ترکیبی با الگوریتم نزول همسایگی متغیر ارائه می کنیم که در حل مشکلات تعادل کامل استاتیک برای برنامه های اشتراک گذاری دوچرخه در مقیاس بزرگ هم مؤثر و هم کارآمد است.

آزمایش های محاسباتی بر روی 1 نمونه مسئله فروشنده مسافرتی تحویل کالا و تحویل کالا (1-PDTSP) که قبلاً در ادبیات استفاده شده بود و روی سه مجموعه جدید از نمونه ها، دو (یکی واقعی و یکی عمومی) بر اساس Share-A- انجام شد. برنامه FFBS Bull Bikes (SABB) اخیراً در پردیس تامپا دانشگاه فلوریدا جنوبی و برنامه دیگر مبتنی بر Divvy SBBS در شیکاگو راه اندازی شده است. آزمایش های محاسباتی روی نمونه های 1-PDTSP نشان می دهد که الگوریتم پیشنهادی از الگوریتم جستجوی تابو بهتر عمل می کند و با الگوریتم های دقیقی که قبلاً در ادبیات برای حل مشکلات تعادل مجدد استاتیک در SBSS گزارش شده اند، رقابتی است. آزمایش های محاسباتی روی نمونه های SABB و Divvy، نشان می دهند که الگوریتم پیشنهادی قادر است با افزایش مقیاس مسئله تعادل مجدد استاتیک مربوط به هر دو FFBS و SBBS مقابله کند، در حالی که راه حل های با کیفیت بالا را در یک زمان معقول CPU استخراج می کند.

معرفی

به اشتراک گذاری دوچرخه به افراد یک روش سالم ، لذت بخش و بدون انتشار برای رفت و آمد در مسافت های کوچک و عاری از نگرانی های داشتن دوچرخه امکان می دهد. همچنین یک راه حل جایگزین و جذاب برای اولین و آخرین مایل در حمل و نقل چند منظوره ارائه می دهد. با گذشت سالها ، طرح های مختلفی از اشتراک دوچرخه ارائه شده است که اولین نسل مربوط به ژوئیه 1965 در آمستردام با ویت فیتسن (دوچرخه های سفید) است. نسل بعدی ، سیستم های سکه سکه ، ابتدا در سال 1991 در دانمارک در فارس و گرنا معرفی شد و سپس در سال 1993 در ناکسکوف در سال 1993 به دست آمد. یک پیشرفت بزرگ هنگامی رخ داد که مردم می توانند از کارت نوار مغناطیسی برای اجاره دوچرخه استفاده کنند. این نسل از اشتراک دوچرخه ، معروف به سیستم مبتنی بر IT با Bikeabout در سال 1996 در دانشگاه پورتسموث ، انگلیس آغاز شد. خوانندگان علاقه مند به Demaio (2009) ، برای مرور کلی در مورد نسل های مختلف به اشتراک گذاری دوچرخه ، مراجعه می کنند.

اشتراک دوچرخه با شناور آزاد (FFBS) نسبتاً جدید است. در این مدل از اشتراک دوچرخه ، دوچرخه ها را می توان به یک قفسه دوچرخه معمولی (یا هر قاب جامد یا مستقل) قفل کرد ، بنابراین نیاز به ایستگاه های خاص را از بین می برد. در مقایسه با اشتراک دوچرخه مستقر در ایستگاه (SBBS) ، FFBS با جلوگیری از ساخت ایستگاه های گران قیمت و ماشین های کیوسک ، هزینه راه اندازی را پس انداز می کند. FFBS با ردیابی دوچرخه در زمان واقعی با GPS داخلی ، از سرقت دوچرخه جلوگیری می کند و فرصت های قابل توجهی را برای مدیریت هوشمند ارائه می دهد. با FFBS ، سطح رضایت مشتری افزایش می یابد زیرا به دست آوردن و بازگشت دوچرخه در مقایسه با SBB ها بسیار راحت تر می شود. میانگین فاصله پیاده روی FFBS کوتاه تر است و مشتریان نیازی به نگرانی در مورد کمبود نقاط خالی در ایستگاه هایی که برای بازگشت دوچرخه نیاز دارند ، نگران نیستند.

SocialBicycles (SOBI) یکی از ارائه دهندگان دوچرخه FFBS است. از دوچرخه های Sobi به عنوان نمونه ای برای نشان دادن نحوه عملکرد FFBS استفاده می شود. هر عضو ثبت شده SOBI یک پین منحصر به فرد دریافت می کند و می تواند از یک برنامه تلفن هوشمند برای یافتن دوچرخه های موجود استفاده کند. پس از رزرو دوچرخه ، کاربر 15 دقیقه برای رسیدن به مکان خود دارد. هنگامی که کاربر دوچرخه را پیدا کرد ، (ها) وارد صفحه کلید داخلی دوچرخه می شود تا دوچرخه را باز کند. اگر کاربر بخواهد به سرعت در جایی متوقف شود ، دوچرخه را می توان قفل کرد و در حالت تعلیق قرار داد. پس از رسیدن به مقصد ، کاربر می تواند دوچرخه را به یک قفسه دوچرخه (یا هر قاب جامد یا مستقل) قفل کند و دوچرخه برای کاربر بعدی در دسترس باشد (شکل 1 را ببینید).

در طول کار روزانه، توزیع دوچرخه ها در سیستم دچار انحراف می شود که اغلب منجر به کیفیت پایین خدمات و نارضایتی کاربر می شود. برای جلوگیری از حاکم شدن چنین سناریویی، اپراتورها دوچرخه ها را در سراسر شبکه جابجا می کنند تا به توزیع مطلوبی دست یابند. عملیات توزیع مجدد دوچرخه ها در سراسر شبکه با استفاده از ناوگان وسیله نقلیه (ها) به عنوان تعادل مجدد دوچرخه شناخته می شود. تعادل مجدد در شب، زمانی که مداخله کاربر ناچیز است، تعادل مجدد ایستا نامیده می شود. اگر مداخله کاربر در نظر گرفته شود، به مشکل تعادل مجدد پویا می گویند. تعادل مجدد دوچرخه یک نوع مشکل مسیریابی وسیله نقلیه است، یک مسئله بهینه سازی ترکیبی چالش برانگیز است که تابع هدف آن به حداقل رساندن هزینه های مالی و زیست محیطی تعادل مجدد است. انواع مختلفی از مشکل تعادل مجدد دوچرخه در ادبیات پیشنهاد شده است، برای بررسی ادبیات مفصل به بخش 2 مراجعه کنید.

بسته به میزان دقیقی که یک تعادل مجدد باید انجام شود، می توان آن را به دو دسته متعادل سازی کامل و جزئی طبقه بندی کرد. در تعادل مجدد کامل، عملیات تعادل مجدد تنها زمانی خاتمه می یابد که موجودی هدف تمام گره های شبکه برآورده شود. با این حال، اگر تعادل مجدد کامل امکان پذیر نباشد (به عنوان مثال: اگر زمان صرف شده برای متعادل کردن کامل سیستم اشتراک دوچرخه بیشتر از زمان واقعی موجود برای تعادل مجدد باشد)، اپراتور ممکن است تعادل بخشی را در نظر بگیرد. در تعادل بخشی مجدد، همه گره ها موجودی هدف خود را برآورده نمی کنند. در SBBS، گره ها ایستگاه های کاری با وضعیت کمبود یا مازاد دوچرخه، یا خودتعادل هستند. FFBS هیچ ایستگاهی مانند SBBS ندارد، بنابراین گره ها در FFBS شامل قفسه های دوچرخه معمولی و مکان های مستقلی هستند که دوچرخه ها توسط کاربران پارک می شوند، و قفسه های دوچرخه و مکان های مستقلی که دوچرخه ها پارک نشده اند، اما به عنوان مکان های مهم برای حضور دوچرخه در نظر گرفته می شوند. اپراتور. برای FFBS، هیچ ایستگاهی مانند SBBS وجود ندارد. در این مطالعه، ما بر روی مسئله تعادل کامل استاتیکی (SCRP) تمرکز می کنیم. تعادل بخشی مجدد تلاش مداوم تیم تحقیقاتی ما است و در مقاله آینده به آن پرداخته خواهد شد. مشکل تعادل مجدد کامل استاتیک (SCRP) از نظر محاسباتی چالش برانگیزتر از مسئله تعادل بخشی استاتیک است، زیرا تعداد دفعاتی که یک گره بازدید می شود، در راه حل بهینه نمی توان از قبل تعیین کرد. ما همچنین در حال انجام مطالعاتی بر روی درک الگوهای تقاضای سیستم اشتراک دوچرخه هستیم و بررسی می کنیم که چگونه تعادل مجدد پویا می تواند در موارد دنیای واقعی اعمال شود.

For the same configuration, i.e., number of stations (in case of SBBS and bike racks in case of FFBS), number of bikes and capacity of the rebalancing fleet, computational complexity of SCRP is higher for FFBS than for SBBS. To illustrate this, let us consider a bike sharing system with 100 stations (or bike racks) and 200 bikes. In case of SBBS, number of locations that the rebalancing vehicle(s) has to visit to completely rebalance the system will at most be 100. This is because some stations may be self rebalanced. However, in case of FFBS, number of locations that the rebalancing vehicle(s) has to visit to completely rebalance the system can at times be ≫ 100 . To illustrate this, let us consider the scenario, when all 200 bikes are parked outside of bike racks in standalone locations but the operator wants each bike rack to have 2 bikes each. In this scenario, number of locations that the rebalancing vehicle(s) has to visit to completely rebalance the system is 300, out of which 200 are standalone locations (for pickup) where bikes are parked and 100 are bike racks (for drop offs). Now, let us consider the scenario when instead of 100 bike racks, the system has 300 bike racks and all 200 bikes are parked outside of bike racks in standalone locations. In this case the operator can have at most 200 bike racks to be filled with 1 bike each. In this scenario, number of locations that the rebalancing vehicle(s) has to visit to completely rebalance the system is at most 400, out of which 200 are standalone locations (for pickup) where bikes are parked and 200 out of 300 bike racks where at least 1 bike needs to be dropped off. Thus we can conclude that nodes in the system that a rebalancing vehicle(s) has to visit is ⩽ Number of Working Stations in case of SBBS and is ⩽ min + Number of Bikes, 2 × Number of Bikes>در مورد FFBS. این واقعیت همچنین از نمونه های زندگی واقعی معرفی شده در بخش 7 مشهود است.

Chemla و همکاران.(2013a) اولین کسی بود که SCRP را برای SBBS معرفی کرد و الگوریتم های جستجوی تابو را برای حل آن ارائه داد. Erdoan و همکاران.. با این حال ، فرمولاسیون های ریاضی ارائه شده در Chemla و همکاران ، 2013a ، Erdoan و همکاران ، 2015 می توانند فقط یک وسیله نقلیه واحد را اداره کنند. علاوه بر این ، زمان فرمولاسیون شبکه گسترده SCRP به گونه ای طراحی شده است که نمی توان آن را برای چندین وسیله نقلیه تمدید کرد. این امر زمانی مشهود است که در آلوارز-والدس و همکاران.(2016) یک روش اکتشافی برای حل SCRP در SBBS برای ناوگان چندین وسیله نقلیه ارائه شده است ، اما نویسندگان قادر به ارائه هیچ فرمول ریاضی نیستند. این مسئله توسط یک فرمول ریاضی بر اساس تجزیه فضایی شبکه به گره های عدم تعادل واحد ، به جز انبار که عدم تعادل آن 0 است ، مورد بررسی قرار می گیرد. بازدید از یک گره توسط همان وسیله نقلیه. برای اطلاعات بیشتر در مورد فرمولاسیون پیشنهادی ، به بخش 3 مراجعه کنید.

جستجوی تابو و الگوریتم های دقیق ارائه شده در Chemla و همکاران ، 2013a ، Erdoan و همکاران ، 2015 ، برای حل مشکلات متعادل کردن استاتیک حتی در FFBS یا SCRP در مقیاس کوچک یا متوسط با وسایل نقلیه متعدد مؤثر نیستند. بنابراین ، در این مطالعه یک الگوریتم اکتشافی ارائه شده است تا راه حل های با کیفیت بالا SCRP را با هر دو وسیله نقلیه منفرد و متعدد ، در مقدار معقول CPU به دست آورد. اکتشافی پیشنهادی شامل ایجاد یک راه حل اولیه با استفاده از اکتشافی ساختمانی حریص و بهبود آن تا زمانی که بهبود دیگری امکان پذیر نباشد. بهبود اکتشافی ترکیبی از تبار متغیر محله با جستجوی بزرگ محله است. هفت اپراتور تبار دانه ای (Toth and Vigo ، 2003) برای نزول متغیر محله استفاده می شود. چهار آشفتگی و سه اپراتور تعمیر ایجاد شد که در نتیجه دوازده محله بزرگ انجام شد. هر یک از این موارد قبل از حرکت به محله بزرگ بعدی ، به طور جامع مورد بررسی قرار می گیرد تا اینکه هیچ پیشرفت دیگری امکان پذیر نباشد و در نتیجه یک جستجوی محله بزرگ تو در تو انجام شود. برای اطلاعات بیشتر در مورد اکتشافی پیشنهادی ، به بخش 4 مراجعه کنید.

آزمایش های محاسباتی در مورد نمونه های 1-PDTSP از ادبیات ، نشان می دهد که الگوریتم ارائه شده از الگوریتم جستجوی تابو (Chemla et al. ، 2013a) بهتر است و با الگوریتم های دقیق (Erdoan et al. ، 2015) برای حل SCRP در بسیار رقابتی است. SBBSقادر است برای 59 از 148 نمونه راه حل های جدیدی پیدا کند که برای آن راه حل بهینه شناخته نشده و به طور متوسط 400 و 36 برابر سریعتر از الگوریتم های جستجوی TABU ارائه شده در ادبیات. آزمایش های محاسباتی در موارد جدید SABB FFBS (متشکل از حداکثر 400 گره ، 300 دوچرخه و اندازه EET حداکثر 3 وسیله نقلیه) و موارد تقسیم شده (متشکل از 450 ایستگاه ، 3000 دوچرخه و اندازه حداکثر 30 وسیله نقلیه)، نشان دهید که NLNS + VND قادر به افزایش مقیاس SCRP برای FFBS و SBB است. همچنین نشان می دهد که SCRP برای هر دو برنامه SABB در USF ، Tampa و Divvy SBB در شیکاگو با اندازه مشخص ناوگان تعادل پذیر امکان پذیر است.

ادامه مقاله به شرح زیر تدوین شده است. بخش 2 SCRP را با جزئیات شرح می دهد و بررسی ادبیات عملیات تعادل در سیستم های اشتراک دوچرخه را ارائه می دهد. بخش 3 فرمولاسیون ریاضی پیشنهادی برای SCRP را توصیف می کند. بخش 4 اکتشافی پیشنهادی ما را برای استخراج راه حل های با کیفیت بالا SCRP توصیف می کند. بخش 5 در مورد استراتژی های پیشنهادی ما برای حل انواع مختلف SCRP با استفاده از روش پیشنهادی ما بحث می کند. بخش 6 مطالعه موردی 1: 1-PDTSP ، 7 مطالعه موردی 2: FFBS Share-A-Bull (SABB) ، 8 مطالعه موردی 3: SBB های Divvy نتایج تجربی و نتیجه گیری از سه مطالعه موردی را خلاصه می کند. بخش 9 مقاله را با دستورالعمل های تحقیقات آینده به پایان می رساند.

قطعه قطعه

توضیحات مشکل و کار مرتبط

در سالهای اخیر ، با رونق SBBS ، تحقیقات گسترده مربوط به سهم دوچرخه انجام شده و مستند شده است. مربوط به مدیریت عملیاتی یک سیستم تقسیم دوچرخه ، این ادبیات را می توان به سه جریان اصلی تحقیق تقسیم کرد: تجزیه و تحلیل تقاضا ، تجزیه و تحلیل سطح خدمات و استراتژی های تعادل. تجزیه و تحلیل سطح خدمات و تقاضا فراتر از محدوده این مطالعه است و در مقاله بعدی که ما روی آن کار می کنیم خلاصه می شود. در این مقاله ، ما فقط روی ادبیات تمرکز می کنیم

فرمول ریاضی SCRP

شبکه تعادل دوچرخه از گره هایی با عدم تعادل غیر صفر و انبار با 0 عدم تعادل تشکیل شده است. شکل 3 نمونه ای از شبکه متشکل از سه گره ، گره 1 یا انبار ، گره 2 با عدم تعادل مثبت 2 (در گره 2 مازاد دو دوچرخه وجود دارد) و گره 3 با عدم تعادل منفی 2 (در گره 3 کسری دو دوچرخه وجود دارد). Erdoan و همکاران.(2015) توانست SCRP را برای ناوگان یک وسیله نقلیه واحد با استفاده از چنین شبکه ای (پس از آن به نام شبکه اصلی) تدوین کند. با این حال،

اکتشافی پیشنهادی

الگوریتم پیشنهادی در این بخش ترکیبی از جستجوی محله بزرگ تو در تو و تبار محله متغیر است. در بقیه مقاله به NLNS + VND گفته می شود. NLNS + VND تا حد زیادی تحت تأثیر موفقیت الگوریتم های متهوریستی مبتنی بر آشفتگی و ترمیم قرار گرفت (Helsgaun ، 2000 ، Helsgaun ، 2009 ، Ahuja et al. ، 2002 ، Applegate et al. ، 2003 ، Ghilas et al. ، 2016) برای حل بزرگدر مقیاس فروشنده مسافر و مشکلات مسیریابی وسیله نقلیه. NLNS + VND می تواند SCRP را در هر دو مورد حل کند

استراتژی های راه حل توصیه شده

• 1. مواردی با عدم تعادل صفر در انبار ، یعنی D 1 = 0 ،
• 2. مواردی با عدم تعادل غیر صفر در انبار ، یعنی D 1 ≠ 0 ،

MILP و NLNS + VND پیشنهادی فقط می توانند مواردی را با عدم تعادل صفر در انبار انجام دهند. در این بخش نشان داده شده است که چگونه می توان نمونه ای با عدم تعادل غیر صفر در انبار را به نمونه ای با عدم تعادل صفر در انبار تبدیل کرد ، به طوری که روش پیشنهادی کاربردی می شود.

مطالعه موردی 1: 1-PDTSP

هدف از مطالعه موردی 1 مقایسه عملکرد NLNS + VND با الگوریتم های دقیق Erdoan و همکاران است.(2015) و الگوریتم های جستجوی تابو از Chemla و همکاران.(2013a).

موارد مورد استفاده در Chemla و همکاران ، 2013a ، Erdoan و همکاران ، 2015 و از موارد 1-PDTSP معرفی شده در هرندز-پروز و سالازار-گونزل (2004) اقتباس شده است. نمونه ها در https://github. com/aritrasep/bsslib. jl در دسترس هستند. آزمایش های محاسباتی در مواردی با α = انجام می شود<1 , 3>، |n |=<20 , 30 , 40 , 50 , 60

مطالعه موردی 2: FFBS Share-A-Bull (SABB)

پردیس Tampa دانشگاه فلوریدا جنوبی 1700 هکتار را در بر می گیرد و بیش از 320 ساختمان را در خود جای داده است. به دلیل شرایط آب و هوایی و وزن سنگین کتابهای درسی ، پیاده روی از یک ساختمان به ساختمان دیگر در طول استراحت بین کلاس ها چالش برانگیز است. بررسی سالانه حمل و نقل و پارکینگ در محوطه دانشگاه تامپا نشان می دهد که افرادی که به دانشگاه می روند ، به طور متوسط یک سفر در تمام محوطه ها را در روز (بین ساختمانها یا ناهار) انجام می دهند. با توجه به اینکه بیش از 38000 دانشجو و 1700 دانشکده وجود دارند

مطالعه موردی 3: SBBS Divvy

Divvy is a large scale SBBS system in the city of Chicago with 476 nodes (stations with a total capacity to hold approximately 7900 bikes), and 4760 bikes. The objectives for conducting this case study are two fold, first, to determine if SCRP with multiple vehicles is feasible for Divvy and second, to determine if NLNS + VND is capable of dealing with increase in complexity of SCRP for large scale SBBS, i.e., when | N |>400 ، 500 ⩽ |ب |و 5 ⩽ |v |بشرموارد آزمایش با استفاده از همان روش مورد استفاده ایجاد می شوند

نتیجه

در مطالعه ما ، یک MILP جدید برای تدوین SCRP در FFBS و SBBS بر اساس تجزیه فضایی گزارش شده است. فرمولاسیون پیشنهادی ، نه تنها می تواند وسایل نقلیه تک و چندگانه را اداره کند ، بلکه امکان بازدید متعدد از یک گره توسط همان وسیله نقلیه را نیز فراهم می کند. فرمولاسیون پیشنهادی حتی برای موارد در مقیاس کوچک به دلیل وجود B Big M ، که برای حذف زیرنویس در محدودیت ها استفاده می شود ، از نظر محاسباتی قابل تحمل است. این باعث می شود آرامش برنامه نویسی خطی فرمول بسیار ضعیف باشد.

سپاسگزاریها

این مطالعه توسط صندوق انرژی سبز دانشجویی (SGEF) در دانشگاه فلوریدا جنوبی پشتیبانی شد. نویسندگان از جوزف فیلدز بخاطر ایجاد نقشه خیابانی باز از دانشگاه USF Tampa و طراحی رابط کاربری برنامه تعادل مجدد USF تشکر می کنند. ما همچنین از سه داوری ناشناس ، برای ارائه نظرات ، پیشنهادات و اصلاحات عمیق در پیش نویس قبلی این مقاله ، بسیار قدردانی می کنیم.