לחסוך בכל מחיר?
02/10/2019
מתלבטים באיזו תחנה כדאי לתדלק? מתברר כי ישנו אלגוריתם היכול לסייע לכם בפתרון הבעיה
בעיית אופטימיזציה היא בעיה שבה מנסים למצוא פתרון שיתן את הערך הקטן ביותר (או הגדול ביותר) עבור משתנה כלשהו. למשל, מהו המסלול הקצר ביותר בין שתי נקודות. בפוסט הנוכחי נדון בבעיית אופטימיזציה שמטרתה לבחור את תחנות הדלק שבהן כדאי לתדלק כדי לחסוך כמה שיותר כסף. למרות שבעיה זו עשויה להצטייר כלא מעניינת במיוחד, היא מעניקה הזדמנות לראות כיצד מתמטיקאים ניגשים לבעיות אופטימיזציה בתחבורה, בעיות הנמצאות במוקד מחקרים ופיתוחים חדשניים.
נתחיל במקרה פשוט: נניח שתוך כדי נסיעה הגענו לצומת דרכים, ואנו נמצאים ליד תחנת דלק שבה הדלק עולה 6 שקלים לליטר. הדרך שלנו ממשיכה 200 ק"מ מערבה, אולם 10 ק"מ מזרחית ישנה תחנה נוספת שבה עולה הדלק 4 שקלים לליטר. היכן כדאי לתדלק כדי לחסוך כסף?
כדי להפוך את השאלה לבעיה מתמטית (תהליך הנקרא "מידול" [1]) אנחנו צריכים מידע נוסף, למשל, מהי כמות הדלק במיכל? מהי צריכת הדלק של הרכב? באיזו מידה החיסכון בזמן שלנו משמעותי? אם נניח שהמכונית שלנו צורכת ליטר בנזין לכל 10 ק"מ, והגענו לצומת עם מיכל ריק, חישוב פשוט יראה שכדי למזער עלות, עלינו למלא ליטר אחד בתחנה הקרובה והיקרה, לנסוע מזרחה, למלא את המכל בתחנה הזולה, ואז לחזור מערבה.
נראה פשוט? בואו נוסיף אילוץ, לפיו תכולת המכל שלנו היא בדיוק 20 ליטר. כעת, אם נמלא דלק בתחנה הזולה, לא יישאר לנו מספיק דלק כדי להגיע ליעד (200 ק"מ מערבה). הפתרון הוא למלא ליטר בתחנה הקרובה, לנסוע מזרחה ולמלא את המכל בתחנה הזולה, לחזור ולמלא שוב ליטר אחד בתחנה היקרה, ואז להמשיך מערבה. הקושי בבעיות אופטימיזציה כאלו, הוא שהן רגישות מאוד לאילוצים השונים בכל מקרה, מה שמקשה מאד על ניסוח אלגוריתם כללי לפתרון.
אחד הניסיונות למצוא אלגוריתם הפותר את בעיית התדלוק, נעשה על ידי מתמטיקאים מאוניברסיטת מרילנד [2], ששאלו: נניח כי עליכם לנסוע בין שתי ערים רחוקות, למשל מניו-יורק לסן-פרנסיסקו, תוך מספר עצירות תדלוק. מה יהיה המסלול המיטבי לחיסכון בכסף?
בפוסט קודם תיארנו אלגוריתם למציאת המסלול הקצר בין שתי ערים [3], אולם כפי שראינו בדוגמה, המסלול הזול הוא לאו דווקא המסלול הקצר. הבעייה שלנו מורכבת יותר, כי לכל תחנת דלק ניתן להגיע בדרכים שונות עם תכולה שונה של מיכל הדלק. כיצד הייתם ניגשים לבעיה?
המתמטיקאים גילו שכדאי דווקא לנתח אותה מהסוף: נניח שפתרנו את הבעיה ונתונה לנו כבר סדרת תחנות הדלק שצריך לבקר בדרך, האם נדע כמה דלק למלא בכל תחנה וכמה בסך הכל זה יעלה?
מהתבוננות בדוגמאות, ניתן להגיע לתשובה פשוטה: כשאנו נמצאים בתחנה כלשהי, נבדוק האם התחנה הבאה בסדרה יקרה יותר. אם כן, כדאי למלא את המיכל עד סופו, כך שכשנגיע אליה, נצטרך למלא פחות דלק. אולם אם התחנה הבאה זולה יותר, נמלא את המינימום הנדרש כדי להגיע אליה עם מיכל ריק. כלומר, המחיר הכולל נקבע רק לפי סדרת התחנות, ומה שנותר לעשות הוא לאתר את הסדרה.
באופן זה, ניתן להפוך את הבעיה לתרגיל מתמטי מסודר. למען הפשטות, נגביל את הכמות המקסימלית של עצירות למספר קבוע K. אנו מחפשים סדרה של עד K תחנות דלק כך שבכל תחנה נתדלק כפי שתארנו בפסקה הקודמת, והתשלום הכולל יהיה מינימלי. ניתן לפתור את הבעיה על ידי בדיקת כל האפשרויות לבחירת סדרות כאלו, אולם דרך זו היא לא יעילה מבחינת זמן חישוב. בכדי שאלגוריתם יהיה שמיש, הוא חייב לפתור את הבעיה בזמן חישוב סביר, מה שקרוי בלשון המתמטיקאים ואנשי מחשבים "פתרון בזמן פולינומאלי". את האלגוריתם שתיארנו ניתן לממש בקוד מחשב כך שיתכנס בזמן פולינומיאלי.
בעיות דומות, אך מורכבות יותר, קיימות בתחום תכנון התחבורה הציבורית: נניח שצריך להגיע למספר יעדים באותו יום, מהו סדר ההגעה האופטימלי כדי לחסוך בדלק? לבעיה זו, שדומה לבעיה קלאסית במדעי המחשב ("בעיית הסוכן הנוסע" [4]) אין פתרון בזמן פולינומאלי, אלא רק פתרונות מקורבים.
תגלית אחרת, פשוטה יותר, יכולה להועיל גם ללא מחשב: אם קבענו את מסלול הנסיעה הכללי מראש וכל שנותר הוא להחליט היכן לעצור ולתדלק על אם הדרך, במקרה זה כדאי למלא בכל תחנה את כמות הדלק המינימלית שתאפשר להגיע לתחנה הבאה הזולה ממנה.
שיטה זו יכולה להועיל לחיסכון, אולם לעתים היא גורמת למצבים קיצוניים. לדוגמה, נניח שאתם נוסעים מזרחה, המכל התרוקן, ואתם מבקשים למלא דלק בתחנה במחיר 4 שקל לליטר. אבל אז, אתם מגלים ש- 100 מטר מזרחה יש תחנה זולה יותר. במצב זה, הפתרון האופטימלי לפי המתמטיקאים הוא לתדלק ב-4 אגורות ואז לעבור לתחנה הבאה....
כפי שרואים, כדי למצוא פתרון הגיוני יש לשלב מספר אילוצים , כמו למשל מחיר וזמן. שאלות כאילו הופכות לרלוונטיות יותר עם התרחבות השימוש באפליקציות ניווט ושיתוף נסיעות, מגמה שתתחזק עם הופעתן של המכוניות האוטונומיות (האם תתנו למכונית להחליט לבד איפה לתדלק?). גם מעבר למכוניות חשמליות מחייב בניית תשתיות חדשות, ומהווה כר נרחב למחקרים יישומיים דומים בשיתוף מתמטיקאים ואנשי מדעי המחשב.
למזלנו, המדינה שלנו קטנה, ואין צורך בעצירות תדלוק רבות בדרך. בינתיים, אפליקציות הניווט ממליצות על דרכי נסיעה מהירות, אולם מחסירות מידע חשוב כמו היכן הקפה טעים יותר…
קישורים ומקורות:
[1] מידול מתמטי ובעיית מילוי דלק
[2] מחקר מתמטי בעיית מילוי הדלק
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
