יותר

מצא נתיב בין מוצא ויעד בהתחשב בנקודות מפוזרות

מצא נתיב בין מוצא ויעד בהתחשב בנקודות מפוזרות


יש לנו מאגר נתונים של postgis המכיל הרבה נקודות ימיות מסודרות (לפי תאריך/שעה) (lat/long). כל אחת מהנקודות הללו מושפעת לרגל בין מוצא ליעד (הן המוצא והן היעד נמצאים על חוף).

על סמך זה אנו מנסים למצוא את כל הנתיבים האפשריים (בתקווה רק אחד ברוב המקרים) עבור כל שילוב מוצא/יעד (כמה רגליים לשילוב נתון), האם מישהו יודע אם קיים כבר סוג של אלגוריתם/פונקציה שעושה זאת ?

עריכה: "מושפע לרגל" פירושו שאנו יכולים למפות כל נקודה שיש לנו לשילוב מוצא-יעד (כך למשל אנו יודעים כי Px (-122 °, 85 °) עבר על ידי כלי שיט את ההפלגה בין מוצא א ויעד ב). מה שאנו קשורים לעשות הוא למצוא את הנתיב הגיאוגרפי האפשרי בין A ו- B על סמך העמדות שאנו יודעים שביקרו בה כלי שיט שעושים את ההפלגה הזו.


זה נשמע שאתה רוצה שאלגוריתם הנתיב הקצר ביותר יפעל על טבלת ה- OD של PostGIS שלך. זה משהו ש- pgrouting יכול לעשות.


ייצוג עולמי של רשת כבישים לתכנון מסלולים ב- GIS

מאמר זה עוסק במתודולוגיה לייצוג נכון של רשת כבישים במערכת המידע הגיאוגרפי (GIS) לניתוח רשתות. עם השנים, העולם האמיתי הפך להיות מורכב מכדי לדגם כראוי בתוך מערכת מידע נתונה, כגון GIS. באופן אידיאלי, כאשר העולם האמיתי מיוצג בצורה מדויקת ככל האפשר, GIS יכול לענות על שאלה בעולמו הווירטואלי המתיישבת עם התשובה המדויקת בעולם האמיתי. עם זאת, שיטות קיימות הקשורות למידול עכבה לכל קטע ברשת כבישים בניתוח תכנון מסלול הכולל רק משתנה מרחק או זמן אינן נותנות תוצאות נכונות. מכאן שמחקר זה בוחן כיצד רשת כבישים יכולה לייצג את העולם האמיתי ב- GIS ולהציע כלים לתכנון מסלולים. כדי לטפל בכך, ראשית, נלקחים בחשבון משתנים מציאותיים נוספים. אלה כוללים מזג אוויר, מידע על ראייה, סוג כביש וכן הלאה. שנית, כדי לשלב משתנים אלה, מוצע מודל עכבה (IM) בשיטת התהליך ההיררכי האנליטי (AHP). לבסוף, כל המודלים מיושמים ומאומתים בעזרת ניתוח רגישות. המודלים יושמו בהצלחה בעבודה זו. כל נתיבי ניתוח תכנון המסלול תואמו בהצלחה לנתיבי הנהגים שבדרך כלל היו נבחרים במציאות. צפוי כי שימוש בטכניקות אחרות כגון תהליך רשת אנליטי (ANP) בנוסף ל- AHP יהיה שימושי להתגבר על הבעיה האמורה.

עיקרי הדברים

◄ אנו קובעים קריטריונים מתאימים שיכולים להציג רשת כבישים במערכת המידע הגיאוגרפי (GIS) לביצוע ניתוחי רשת ביעילות. ◄ אנו מדגמים ומשלבים את הקריטריונים המשוקללים באמצעות טכניקות AHP כדי לקבל מודלים של עכבה. ◄ אנו מעריכים את המודלים הנגזרים באמצעות טכניקת ניתוח רגישות מודל. ◄ אנו משתמשים בתוכנת בחירת מומחים לניתוחי רגישות המודל.


בעיית התחבורה הקלאסית נוגעת להקטנת עלות הובלת מוצר יחיד ממקורות ליעדים. זוהי בעיה של זרימת רשת המתעוררת בלוגיסטיקה תעשייתית ונחשבת למקרה מיוחד של תכנות לינארי. המספר הכולל של היחידות המיוצרות בכל מקור, המספר הכולל של היחידות הנדרשות בכל יעד והעלות להובלת יחידה אחת מכל מקור לכל יעד הן התשומות הבסיסיות. המטרה היא למזער את העלות הכוללת של הובלת היחידות המיוצרות במקורות כדי לענות על הדרישות ביעדים. פתרון הבעיה כולל שלושה שלבים בסיסיים: 1) מציאת פתרון בסיסי ראשוני אפשרי, 2) בדיקה אם הפתרון הנוכחי הוא אופטימלי (בעל העלויות הנמוכות ביותר) ו- 3) שיפור הפתרון הנוכחי באמצעות איטרציה. דוגמנות ופתרון בעיית התחבורה הקלאסית מסתמכות מאוד על מודלים של רשתות, אלגוריתמים של הנתיב הזול ביותר וניתוח הקצאת מיקום בתחום מדעי המידע הגיאוגרפי (GIScience). לפיכך, הוא מייצג מרכיב מרכזי בתחום ניתוח הרשת והדוגמנות של GIS & ampT.

שיר, י '(2017). בעיית התחבורה הקלאסית. מדע המידע הגיאוגרפי וטכנולוגיית גוף הידע (מהדורה רביעית 2017), ג'ון פ. וילסון (עורך). DOI: 10.22224/gistbok/2017.4.7

גרסה זו פורסמה ב- 15 בנובמבר 2017.

נושא זה זמין גם במהדורות הבאות: DiBiase, D., DeMers, M., Johnson, A., Kemp, K., Luck, A. T., Plewe, B., and Wentz, E. (2006). בעיית התחבורה הקלאסית. מדע המידע הגיאוגרפי וטכנולוגיית גוף הידע. וושינגטון הבירה: איגוד הגאוגרפים האמריקאים. (רבעון שני 2016, דיגיטל ראשון).

רשתות: ניתן להגדיר רשת כגרף מכוון G = (V, A) כאשר V הוא קבוצת הקודקודים או הצמתים, ו- A היא קבוצת הקשתות או הקישורים המתאימים לנתיבים האפשריים בין הצמתים. כל קשת/קישור מוקצה לעתים קרובות עם משקל המשקף את עלות התנועה וכמה אילוצים נוספים (למשל יכולות זרימה).

תכנות לינארי: ניתן להגדיר בעיית תכנות לינארית כבעיה של הגדלת/מזעור פונקציה לינארית הכפופה לאילוצים ליניאריים. האילוצים יכולים להיות שוויון או אי שוויון. הפונקציה הלינארית שיש למזער/למקסם היא הפונקציה האובייקטיבית.

לוגיסטיקה תעשייתית: באופן כללי, לוגיסטיקה תעשייתית היא ניהול המשאבים בין מקורות ליעדים כדי לענות על דרישות של לקוחות או תאגידים. המשאבים כוללים פריטים פיזיים כגון מזון וציוד, ומופשטים כגון זמן ומשאבים.

הֵאוֹרִיסטִי: היוריסטי עוסק באופטימיות, שלמות, דיוק ו/או דיוק למהירות תוך פתרון בעיה. בהתבסס על מידע זמין, יוריסט מדרג את החלופות בכל שלב כדי להחליט לאיזה כיוון לפעול. למשל, היוריסט חמדני בוחר ערך אופטימלי מקומי בכל שלב, ומנסה למצוא אופטימום גלובלי.

בעיית התחבורה הקלאסית היא כבר מזמן בעיית מחקר חיונית בתחום הלוגיסטיקה התעשייתית והתחבורתית. הבעיה מונעת מהצורך בהובלת מצרך יחיד ממקורות (מפעלים ומפעלים) ליעדים (מחסנים ושווקי צרכנים). ההנחה היא כי סך היחידות המיוצרות בכל מקור, סך היחידות הנדרשות על ידי כל יעד, עלות הובלת יחידה אחת מכל מקור לכל יעד. והמטרה היא למזער את העלות הכוללת של יחידות המשלוח ממקורות כדי לעמוד בדרישות ביעדים. הבעיה מונעת גם מהצורך להעביר אנשים בין מקומות פעילות כגון בית ומשרד. במודלים מסורתיים של ארבעה שלבים, ניתן ליישם את הבעיה בהפצת טיולים בין אזורי מוצא ואזורי יעד (a.k.a. חלוקת טיולים).

בעיית התחבורה הקלאסית היא בעיית רשת אופיינית. המקורות והיעדים מיוצגים כ צמתים, ונתיב התחבורה מכל מקור לכל יעד מיוצג כ- קישור. איור 1 מייצג מודל רשת עם M מקורות ו נ יַעַד.

איור 1. הובלת מצרך ממקורות ליעדים, אאני ו באני ציינו יחידות המסופקות ויחידות המבוקשות.

מספר זה מסופק לפי מקור אני הוא אאני, ל אני = 1, 2, . M. מספר היחידות הנדרשות ליעד י הוא בי, ל י = 1, 2, . נ. עלות הובלת יחידה אחת לאורך הקישור מהמקור אני ליעד י הוא גij, ומספר היחידות המועברות לאורך הקישור הוא איקסij. העלות הכוללת של הובלת יחידות מהמקור אני לכל היעדים <י> הוא:

באופן דומה העלות הכוללת של הובלת יחידות ליעדים j מכל המקורות <אני> הוא:

לפיכך, ניתן לנסח את בעיית התחבורה הקלאסית כמשוואה לינארית:

משוואה (3) מייצגת את עלות ההובלה הכוללת והיא הפונקציה האובייקטיבית של בעיית ההובלה הקלאסית. משוואה (4) מציינת כי סך היחידות שנשלחו מהמקור אני לא יעלה על היחידות הזמינות אאני במקור אני. משוואה (5) מציינת כי סך היחידות שנשלחו ליעד י צריך לענות על דרישתו בי.

מודל הרשת לעיל יכול להיות מאוזן או לא מאוזן. כאשר סך ההיצע בכל המשאבים, שווה לביקוש הכולל בכל היעדים, המודל מאוזן. אחרת, המודל אינו מאוזן, עם עודף ביקוש או עודף היצע. במקרה של עודף ביקוש,, נוצר מקור דמה שישקף את עלות הקנס, פ, לכל יחידה של דרישה לא מספקת. במקרה של עודף היצע,, מחסן דמה נוצר כדי לשקף את עלות האחסון ס לכל יחידת ייצור עודף.

מלבד השימוש במשוואות, ניתן גם לנסח את בעיית התחבורה הקלאסית כמטריצות. איור 2 מציג מודל רשת מאוזן עם M מקור ו נ יעדים.

איור 2. מודל רשת מאוזן שנוסח כמטריצה.

ניתן לנסח את בעיית התחבורה הקלאסית באמצעות משוואות (3) עד (6), שכולן משוואות לינאריות. מכאן שניתן לבנות את הבעיה כתוכנית לינארית ולפתור אותה באמצעות שיטת סימפלקס. שלושת השלבים הם: 1) מציאת פתרון בסיסי ראשי אפשרי, 2) בדיקה אם הפתרון אופטימלי ו -3) שמירה על שיפור הפתרון.

3.1 מציאת פתרון בסיסי ראשי אפשרי

לבעיית התחבורה המאוזנת, האילוצים שנקבעו במשוואה (4) ו- (5) מנוסחים מחדש כשאלות לינאריות:

מכיוון שההיצע הכולל שווה לביקוש הכולל, יש לנו:

לכן אחת המשוואות במערך האילוצים מיותרת, והמספר הכולל של המשוואות הבלתי תלויות הופך ל (M + נ - 1). זה בגלל שאם אאני, אני = 1, 2, . M ו בי, י = 1, 2, . (נ-1) מפורטים, בנ ניתן לחשב כ. בתוכנית לינארית, המשתנים הבסיסיים מופנים למשתנים שאינם אפסים, ומספר המשתנים הבסיסיים בפתרון בסיסי אפשרי זהה למספר משוואות האילוץ הבלתי תלויות (לונברגר ויה, 2015). לכן, פתרונות לבעיית התחבורה המאוזנת צריכים להיות בדיוק (M + נ - 1) משתנים בסיסיים הנותרים (mn - M - נ + 1) משתנים הם משתנים לא בסיסיים ושווים לאפס.

השיטות הנפוצות ליצירת פתרון בסיסי ראשי אפשרי כוללות: 1) שיטת פינה צפון -מערבית, 2) שיטת מטריצה ​​מינימלית (שיטת העלות הזולה ביותר), 3) שיטת מינימום שורה או עמודות מינימליות ו -4) שיטת קירוב של פוגל. בהתחשב בבעיה שנוסחה כמטריצה ​​(ראה איור 2), שיטת הפינה הצפון מערבית פשוט מתחילה בפינה הצפון מערבית של המטריצה ​​ומקצה איקס11 ושלוש השיטות האחרות מנסות ליצור פתרון ראשוני "קרוב יותר" לפתרון האופטימלי על ידי הקצאת יחידות נוספות לתאי מטריצה ​​בעלויות נמוכות יותר גij .

איור 3 הוא דוגמה לשיטת הפינה הצפון מערבית. השיטה מתחילה בתא בפינה הצפון מערבית ממקור 1 ליעד 1, איקס11 . מכיוון שהביקוש מהיעד 1 הוא 5 יחידות וההיצע מהמקור 1 הוא 8 יחידות, התא איקס11 לוקח את הערך הקטן יותר 5 יחידות. מאחר ולשורה הראשונה נותרו 3 יחידות, השיטה נעה צעד אחד מזרחה ומעבדת את התא איקס12 . בעמודה השנייה נותרו 9 יחידות ולשורה הראשונה 3 יחידות ולכן התא איקס12 לוקח את הערך 3 יחידות. כעת, לעמודה השנייה נותרו 6 יחידות, כך שהשיטה נעה צעד אחד דרומה ומעבדת את התא איקס22. בכל אחד מהשלבים הבאים השיטה נעה צעד אחד מזרחה או לדרום והתא לוקח את הערך הקטן יותר שנותר בעמודה ובשורה שלו. השיטה נעצרת כשהיא מגיעה לפינה המזרחית-דרוםית של המטריצה.

איור 3. מציאת פתרון בסיסי ראשי אפשרי בשיטת הפינה הצפון מערבית.

3.2 בדוק את האופטימיות

בהתחשב בפתרון ההתחלתי הבסיסי הראשוני, השלב הבא הוא לבדוק אם הפתרון הנוכחי הוא אופטימלי. ניתן לנסח את קריטריוני האופטימיזציה על ידי הגדרת שתי מערכות עלויות צל עבור הפתרון הנוכחי <איקסij>: 1) עלות משלוח uאני להעביר יחידה אחת מהמקור אני לכל יעד, ו 2) עלות קבלה vילהעביר יחידה אחת ליעד י מכל מקור שהוא. עלויות צל אלה צריכות לספק:

מכאן שהפתרון הנוכחי הוא אופטימלי אם משתנים לא בסיסיים אינם יכולים להציע עלויות נמוכות יותר:

ניתן ליישם קריטריוני אופטימיזציה אלה על ידי קביעת ערכים של <uאני> ו <vאני> מבוסס על משוואה (10), חישוב הפרשי עלויות עבור כל המשתנים הלא בסיסיים, ובדיקה אם כולם אינם שליליים. מכיוון שמספר המשתנים הבסיסיים בפתרון האפשרי הבסיסי הוא (M + נ - 1) והמספר הכולל של מחירי הצל <uאני, vי> הוא (M + נ), תמיד נוכל למצוא פתרון בסיסי ל <uאני, vי>. זה נפוץ להגדיר u1 = 0. איור 4 מציג דוגמה המבוססת על הפתרון הבסיסי הראשוני הניתן באיור 3, הפרשי המחירים ממוקמים בפינות התחתונות השמאליות. בהתחשב בתוצאת החישוב, הפתרון הבסיסי הראשוני הניתן לביצוע אינו אופטימלי מכיוון שהפרשי העלויות שליליים.

איור 4. בדיקת הפחתות מחירים אפשריות.

3.3 שיפור הפתרון באמצעות איטרציה

אם הפתרון הנוכחי אינו אופטימלי, יש לפחות משתנים לא בסיסיים איקסij = 0 עם הפרש עלויות שיכול להפחית את עלות ההובלה הכוללת של המערכת. שיטה ישירה ואפשרית לשיפור הפתרון היא להגדיר את המשתנה הלא בסיסי עם יחידות המשלוח המתאימות ביותר ולגדול ביותר איקסuv עד כמה שאפשר. למשל, ההבדל השלילי ביותר הוא באיור 4 ואם איקס32 אם הוא יגדל ב-, הוא ישבור את הרצף המשמש ליצירת הפתרון הבסיסי הראשוני, החל מ- x22. כתוצאה מכך, יש לנו משתנים בסיסיים המותאמים כ-. מכיוון שאנו זקוקים למשתנים מותאמים כדי שלא יהיו שליליים, = 1 ניתן על ידי. לאחר התאמת המשתנים הבסיסיים, הפתרון משתפר והופך להיות עדכני. אלא אם כן הפתרון הנוכחי הוא אופטימלי, אנו חוזרים על הליך השיפור לעיל.

הרחבות עיקריות של הניסוחים והפתרונות של בעיית התחבורה הקלאסית לעיל הן: 1) הצגת תחנות העברה בינוניות (aka hubs network) (O'Kelly and Miller, 1994), 2) בהתחשב בשינויים בכמויות הביקוש והביקוש ותחבורה יחידה דינאמית. עלויות (aka בעיית תחבורה דינמית) (Powell et al. 1995), 3) הוספת אילוצים המשקפים את יכולות הרשת ו/או הטעינה (נחמיאס אנד צ'נג, 1993), ו 4) הצבת יעדים מרובים לצד צמצום עלויות המשלוח (Ulungu & amp Teghem , 1994). הרחבות אלה תואמות תרחישי תכנון ותפעול בעולם האמיתי ומשפרים את היתרונות הפרקטיים של המודל הבסיסי אולם הם גם מביאים אתגרים גדולים, במיוחד בהתמודדות עם רשתות גדולות.

הרבה חבילות תוכנה קיימות לאופטימיזציה כוללות פותרי תכנות לינארי. חלק מהחבילות דורשות מהמשתמשים לרכוש רישיונות כגון LGO (Lipschitz-Global Optimizer Optimizer) ו- MINOPT (A Modeling Language and Algorithmic Framework for Linear, Mixed-Integer, Nonlinear, Dynamic, and Mixed-Integer Nonlinear Optimization). חלק מהחבילות מספקות גרסאות חינמיות עם פונקציות מוגבלות וגירסאות מלאות ברכישה כגון GAMS (מערכת דוגמנות אלגברית כללית) ו- LINDO (לינארית, אינטראקטיבית וייעול אופטימיזציה). חלקן זמינות כחבילות קוד פתוח כגון AMPL (שפת דוגמנות לתכנות מתמטי). לבעיות המורכבות והרשת הגדולה, פותרים אלה בדרך כלל מיישמים היוריסטיקה כדי להפחית את המורכבות החישובית. בנוסף, אלגוריתמים שונים הופעלו לשיפור תהליך הניסוח, הפתרון וההערכה. כמה שיטות נפוצות הן שיטות מטושטשות ונוירו-מטושטשות, אלגוריתמים גנטיים, חיפוש טאבו וגישות ענף וקשורות (Srivastava, 2007).

מערכות מידע גיאוגרפיות לתחבורה (GIS-T) עוסקות במידע על מערכות התחבורה הקשורות להן, והוכרו כיישום מרכזי של מדעי המידע הגיאוגרפי (GIS) (מילר ושו, 2001). ביחס לבעיית התחבורה הקלאסית, GIS-T מספקת מודלים ואלגוריתמים לאיסוף, ניהול, ניתוח והפצת מידע מרחבי. אלה כוללים, אך אינם מגבילים, איסוף או אומדן אספקה ​​ודרישות, דוגמנות ואחסון של רשתות התחבורה, חישוב נתיבים בעלות נמוכה ביותר לקביעת עלויות הובלה יחידה ותמיכה בניתוחים מורכבים יותר (למשל עלויות דינאמיות ורב-מטרות) .

בכמה חבילות תוכנה של GIS יש פתרונות תכנות ליניאריים המוטמעים בהם (למשל TransCAD על ידי חברת Caliper Corporation, CPLEX על ידי ILOG, Xpress-MP על ידי אופטימיזציית Dash ו- ArcGIS של Esri). ישנן גם כמה חבילות GIS בעלות קוד פתוח (כגון LP-Solver מאת מישל ברקלאר באוניברסיטת טכנולוגיה באיינדהובן). למרות ש- LINDO וחבילות אופטימיזציה אחרות הן חזקות וגמישות יותר בעת פתרון תוכנות לינאריות, חבילות GIS יכולות לספק תמיכה נוספת להגדרת הבעיה ולשינויה ולמידע המידע. לדוגמה, תוכנת GIS יכולה להציג באופן ישיר התפלגויות מרחביות של המקור ואתרי היעד, ואת כמות האספקה ​​והדרישות באותם מיקומים. זה יאפשר חקירה ויזואלית של הבעיה וזיהוי שגיאות אפשריות הקיימות בנתונים (למשל מיקומים לא נכונים ויחידות סך הכל לא ריאליות). דוגמה נוספת היא כלי GIS שיכולים לחשב נתיבים עם המחיר הזול ביותר בין מקורות ליעדים, ולהפיק את מטריצת העלות המתאימה לכל המקורות והיעדים. בהשוואה למרחקים אוקלידיים, מטריצת מרחק זו יכולה לספק הערכה מדויקת יותר של עלויות המשלוח.

דוגמה מיוחדת לסוג זה של כלי GIS היא שכבת ניתוח הקצאת המיקומים בתוסף אנליסט הרשת המסופק על ידי ArcGIS של Esri. ראשית, הוא מאפשר למשתמשים לייבא או לאתר ידנית מתקנים (מקורות) ולבקש נקודות (יעדים). שנית, הכלי מאפשר למשתמשים להקצות או לעדכן חומרים ודרישות במיקומים אלה. שלישית, ניתן לעדכן את הרשת הבסיסית כך שתשקף את מצב התנועה ואת המהירויות הניתנות להשגה. רביעית, הכלי מספק אפשרויות שונות למטרות בעיה, כגון מזעור עכבה, מיקסום הכיסוי ומקסום נתח שוק. אחרון חביב, התוצאות קשורות לכל מתקן ונקודת ביקוש, כל עוד קישורים עמוסים ביחידות שיועברו בין מקורות ליעדים.

בעיית התחבורה הקלאסית ב- GIScience מהמאה ה -21 מתמודדת עם הזדמנויות ואתגרים חדשים (מילר ושו 2015). ראשית, הדרישות הגוברות לסחר ולנסיעות בינלאומיות דורשות מערכות תחבורה יעילות יותר להעביר אנשים וסחורות ברחבי העולם. שנית, ההתקדמות בטכנולוגיות מידע ותקשורת (ICT) וטכנולוגיות המודעות למיקום (LAT) מאפשרות לנו לאסוף כמויות גדולות של נתונים ולהפיק דרישות משתמש עדכניות וזמני הובלה בין מיקומים. עם זאת, הפופולריות של ICT ו- LAT גם מביאה אתגרים חדשים לבעיה. למשל, פופולריות משתנה לקניות מקוונות מובילה לדרישות מפוזרות יותר, ומסתמכות יותר על מחסנים כתחנות ביניים להפצה.

Luenberger, D. G., & amp Ye, Y. (2015). תכנות לינארי ולא לינארי (כרך 228). ספרינגר.

מילר, ח 'ג'יי, ושו, ס' ל (2001). מערכות מידע גיאוגרפיות לתחבורה: עקרונות ויישומים. הוצאת אוניברסיטת אוקספורד לפי דרישה.

מילר, ח 'ג'יי, אנד שו, ס' ל (2015). מערכות מידע גיאוגרפיות לתחבורה במאה ה -21. מצפן גיאוגרפיה, 9(4), 180-189. DOI: 10.1111/gec3.12204

נחמיאס, ס ', אנד צ'נג, י' (1993). ניתוח ייצור ותפעול (כרך 2). Homewood, IL: ארווין.

או'קלי, מ ', ומילר, ח' ג'יי (1994). הבעיה בעיצוב רשת הרכזת: סקירה וסינתזה. כתב העת לגיאוגרפיה של תחבורה, 2(1), 31-40.

פאוול, ווב, ג'ילט, פ 'ואודוני, א' (1995). רשתות וניתוב סטוכסטי ודינמי. ספרי יד במחקר ותפעול מדעי הניהול, 8, 141-295.

Srivastava, S. K. (2007). ניהול שרשרת אספקה ​​ירוקה: סקירת ספרות חדישה. כתב העת הבינלאומי לניהול ניהול, 9(1), 53-80. DOI: 10.1111/j.1468-2370.2007.00202.x

Ulungu, E. L. & amp Teghem, J. (1994). בעיות אופטימיזציה קומבינטוריות רב-אובייקטיביות: סקר. כתב העת לניתוח החלטות מרובות קריטריונים, 3(2), 83-104.


פרמטר החיישן

ממשק API של מפות Google דרש בעבר לכלול את פרמטר החיישן כדי לציין אם היישום שלך השתמש בחיישן כדי לקבוע את מיקומו של המשתמש. פרמטר זה אינו נדרש עוד.

אלא אם צוין אחרת, תוכן דף זה מורשה תחת רישיון Creative Commons Attribution 4.0, ודוגמאות קוד מורשות תחת רישיון Apache 2.0. לפרטים, עיין במדיניות האתר של מפתחי Google. Java הוא סימן מסחרי רשום של Oracle ו/או שלוחותיה.


סקר זרימת סחורות 2012

סקר זרימת הסחורות (CFS) הוא מאמץ משותף של הלשכה לסטטיסטיקה של תחבורה (BTS) ולשכת המפקד האמריקאית, משרד המסחר האמריקאי. הסקר הוא המקור העיקרי לנתונים ברמה הלאומית והמדינה על משלוחי משא ביתי על ידי מוסדות כרייה, ייצור, סיטונאות, עזר ותעשיות מסחר קמעונאיות ושירותים הנמצאות ב -50 המדינות ובמחוז קולומביה. הנתונים ניתנים על סוג, מוצא ויעד, ערך, משקל, דרכי תחבורה, מרחק שנשלח וטונות קילומטרים של סחורות שנשלחו. ה- CFS מתנהל כל 5 שנים כחלק מהמפקד הכלכלי. הוא מספק תמונה מודאלית של זרמי הובלה לאומיים ומייצג את המקור היחיד הזמין לציבור לנתוני זרימת סחורות עבור מצב הכביש המהיר. ה- CFS נערך בשנים 1993, 1997, 2002, 2007, ולאחרונה בשנת 2012.

CFS מעריך את הביקוש למתקני ושירותי תחבורה, שימוש באנרגיה, סיכון בטיחותי וסביבתי. נתוני CFS משמשים קובעי מדיניות ומתכנני תחבורה בסוכנויות פדרליות, ממלכתיות ומקומיות שונות. בנוסף, בעלי עסקים, חוקרים פרטיים ואנליסטים משתמשים בנתוני CFS לצורך ניתוח מגמות בתנועת סחורות, מיפוי דפוסים מרחביים של סחורות וזרימות רכב, חיזוי דרישות לתנועה של סחורות וקביעת צרכים לתשתיות וציוד נלווים.

תְחוּם

כיסוי בתעשייה

CFS לשנת 2012 מכסה מפעלים עסקיים עם עובדים בתשלום הנמצאים בארצות הברית ומסווגים באמצעות מערכת סיווג התעשייה הצפון אמריקאית לשנת 2007 (NAICS) בענפי כרייה, ייצור, סיטונאות ותעשיית קמעונאות ושירותים נבחרים, כלומר קניות אלקטרוניות ו בתי הזמנת דואר, סוחרי דלק ומוציאים לאור. בנוסף, הסקר מכסה מפעלים עזר (כלומר, מחסנים וניהול משרדים) של חברות רב -ממסדיות.

בגין CFS לשנת 2012 נערך בשנת 2011 סקר מקדים (טרום קדם) ממוקד לשיפור איכות הנתונים על המסגרת לענפים או סוגים של מפעלים. הקבוצות שנכללו בסקר מוקדם זה היו:

קבוצת סקר מוקדמת מספר מפעלים
עזר (NAICS 484, 4931, 551114). 34,985
מפעלים קטנים לקניות והזמנת דואר אלקטרוני (NAICS 4541). 13,431
מוציאים לאור קטנים (NAICS 5111). 11,804
מפעלים גדולים. 39,608
סך הכל. 99,828

עבור שלוש הקבוצות הראשונות, המטרה הייתה לזהות את אותם מפעלים המפעילים בפועל פעילויות שילוח. בקבוצות אלה, מפעלים שנסקרו שדיווחו כי לא ביצעו כל פעילות משלוחים לא נכללו ביקום מדגם ה- CFS בסופו של דבר. עבור מפעלים גדולים המטרה הייתה להשיג מדד מדויק של פעילות הספנות שלהם.

תעשיות CFS

תעשיות בהיקף ל- CFS 2012 נבחרו על סמך NAICS לשנת 2007. תעשיות שנכללו ב- CFS 2007 ו -2002 נבחרו בהתבסס על גרסאות ה- NAICS משנת 2002 ו -1997 בהתאמה. הענפים ב -1999 CFS ו- 1993 CFS נבחרו על בסיס מערכת הסיווג התעשייתי הסטנדרטית (SIC) משנת 1987, ולמרות שנעשו ניסיונות לשמור על כיסוי דומה בקרב הסקרים המבוססים על SIC (1993 ו -1997) והסקרים המבוססים על NAICS (2002 , 2007 ו- 2012), חלו כמה שינויים בכיסוי הענף עקב ההמרה מ- SIC ל- NAICS. ראוי לציין כי הכיסוי של תעשיית הכריתה השתנה מתעשייה בהיקף (SIC 2411) למגזר החסר של תחום החקלאות, היערות, הדיג והציד במסגרת NAICS 1133. כמו כן, בעלי אתרים סווגו מחדש מתעשייה (SIC 2711 , 2721, 2731, 2741, וחלק מ- 2771) למידע (NAICS 5111 ו- 51223) והוחרגו ב- CFS משנת 2002. עם זאת, 2007 ו- 2012 CFS כוללים אתרים וסוחרי דלק קמעונאיים.

ענפי NAICS (2007) המכוסים ב- CFS לשנת 2012 מפורטים בטבלה הבאה:

קוד NAICS תיאור
212 כרייה (למעט נפט וגז)
311 ייצור מזון
312 ייצור מוצרי משקאות וטבק
313 טחנות טקסטיל
314 טחנות מוצרי טקסטיל
315 ייצור בגדים
316 ייצור עור ומוצרי ברית
321 ייצור מוצרי עץ
322 ייצור נייר
323 1 פעילויות הדפסה ותמיכה נלוות (למעט 323122)
324 ייצור מוצרי נפט ופחם
325 ייצור כימי
326 ייצור מוצרי פלסטיק וגומי
327 ייצור מוצרים מינרליים לא מתכתיים
331 ייצור מתכת ראשונית
332 ייצור מוצרי מתכת מיוצרים
333 ייצור מכונות
334 ייצור מחשבים ומוצרים אלקטרוניים
335 ציוד חשמלי, מכשירי חשמל וייצור רכיבים
336 ייצור ציוד תחבורה
337 ייצור רהיטים ומוצרים נלווים
339 ייצור שונות
4231 2 סיטונאים של סוחרי רכב וחלקים
4232 2 ריהוט וסיטונאים סוחרים של ריהוט ביתי
4233 2 עץ וחומרי בנייה אחרים סיטונאים סוחרים
4234 2 ציוד מסחרי. סיטונאים סוחרים
4235 2 מתכת ומינרלים (למעט נפט) סיטונאים סוחרים
4236 2 מוצרי סיטונאים של סוחרי חשמל ואלקטרוניקה
4237 2 סיטונאים סוחרי חומרה ואינסטלציה
4238 2 מכונות, ציוד ואספקה ​​של סיטונאים סוחרים
4239 2 מוצרי סיטונאי סוחרים שונים
4241 2 סיטונאים סוחרים של נייר ומוצרי נייר
4242 2 סיטונאים סוחרים של תרופות וסמים
4243 2 הלבשה, פריטי פריטים ורעיונות סיטונאים סוחרים
4244 2 מכולת וסיטונאים סוחרים של מוצרים נלווים
4245 2 מוצרי גלם סיטונאים סוחרים של חומרי גלם
4246 2 סיטונאים סוחרים של מוצרים כימיים ובעלי ברית
4247 2 נפט ומוצרי נפט סיטונאים סוחרים
4248 2 סיטונאים סוחרים של בירה, יין ומשקאות אלכוהוליים מזוקקים
4249 2 מוצרים סיטונאיים סוחרים שונים
4541 קניות אלקטרוניות ובתי הזמנות בדואר
45431 סוחרי דלק
4841 3 הובלות כלליות
4842 3 הובלות הובלה מיוחדות
4931 3 אחסון ואחסון
5111 4 מוציאים לאור עיתונים, כתבי עת, ספרים ומדריך
551114 5 משרדי ניהול, תאגיד ותאגיד אזורי

1 לא כולל שירותי Prepress (NAICS 323122). 2 מפעלים סיטונאיים אינם כוללים משרדי מכירה של יצרנים ויבואני מותגים. 3 כולל רק מחסנים שבוי המספקים תמיכת אחסון ומשלוח לחברה אחת. מחסנים המציעים את שירותיהם לציבור הרחב ולעסקים אחרים אינם נכללים. NAICS 4841 ו- 4842 הם תעשיות חדשות ל CFS 2012. לצורכי טבלאות ופרסום, NAICS 484 מקובץ עם NAICS 4931. 4 בשנת 2007, NAICS 51223 מוציאים לאור מוציאים לאור ופורסמו ב- NAICS 5111. עם זאת, עבור מחזור 2012, NAICS 51223 לא נדגם. 5 כולל רק את אותם מפעלים ב- NAICS 551114 עם פעילות משלוחים. הערות: תעשיות לא נכללות: מפעלים זרים, מפעלים המסווגים בתחבורה, בנייה ורוב ענפי הקמעונאות והשירותים אינם נכללים. אזורי תעשייה אחרים שאינם מכוסים, אך עשויים להיות בעלי פעילות ספנות משמעותית, כוללים חקלאות וממשל. במיוחד לחקלאות, המשמעות היא ש- CFS אינו מכסה הובלות של מוצרים חקלאיים מאתר החווה למרכזי העיבוד או מעליות הטרמינל (סביר להניח שתנועות מקומיות למרחקים קצרים), אלא מכסות את המשלוחים של מוצרים אלה מהעיבוד הראשוני. מרכזים או מעליות סופניות הלאה. אי הכללות כלליות: נתונים על מפעלים המופעלים על ידי הממשלה אינם נכללים ב- CFS. אלה כוללים שירותים ציבוריים, מערכות אוטובוס ורכבת תחתית, ספריות ציבוריות ובתי חולים בבעלות ממשלתית. CFS גם אינו כולל מפעלים או חברות ללא עובדים בתשלום.

כיסוי משלוח

ה- CFS לוכד נתונים על משלוחים שמקורם בסוגים נבחרים של מפעלים עסקיים הממוקמים ב -50 המדינות ובמחוז קולומביה. ה- CFS אינו מכסה משלוחים שמקורם במפעלים עסקיים הממוקמים בפורטו ריקו וברכוש וטריטוריות אחרות בארה"ב. באופן דומה, משלוחים החוצים את ארצות הברית ממיקום זר למיקום זר אחר (למשל מקנדה למקסיקו) אינם כלולים, וגם לא משלוחים ממיקום זר למיקום ראשוני בארה"ב. עם זאת, מוצרים מיובאים כלולים ב- CFS מרגע שהם עוזבים את המיקום הראשוני של היבואן בארה"ב למשלוח למקום אחר.

משלוחים שנשלחים דרך שטח זר עם מוצאם והיעד בארצות הברית כלולים בנתוני CFS. הקילומטראז 'המחושב למשלוחים אלה אינו כולל את פלחי המדינה הזרה (למשל, משלוחים מניו יורק למישיגן דרך קנדה אינם כוללים קילומטראז' לקנדה). משלוחי ייצוא כלולים, כאשר היעד המקומי מוגדר כנמל, שדה תעופה או מעבר גבול של יציאה מארצות הברית. עיין בסעיף חישוב קילומטראז לפרטים נוספים על אופן פיתוח אומדני הקילומטראז '.

איסוף נתונים

כל מוסד שנבחר במדגם ה- CFS נשלח בדואר שאלון לכל אחד מארבעת שבועות הדיווח שלו, כלומר, לממסד נשלח שאלון אחת לרבעון של 2012. עבור מפעל נתון, המשיב התבקש לספק את המידע הבא אודות כל על המשלוחים המדווחים של הממסד:

  • מספר מזהה משלוח
  • תאריך משלוח (חודש, יום)
  • ערך המשלוח
  • משקל המשלוח בפאונד
  • קוד סחורה מרשימת הסיווג הסטנדרטי של מוצרים מועברים (SCTG)
  • תיאור סחורה
  • אינדיקציה אם המשלוח היה מבוקר טמפרטורה
  • מספר האו"ם או צפון אמריקה (UN/NA) למשלוח חומרים מסוכנים
  • יעד ארה"ב (עיר, מדינה, מיקוד) - או שער למשלוח יצוא
  • אופני הובלה
  • אינדיקציה אם המשלוח היה יצוא
  • עיר ומדינת היעד לייצוא
  • מצב ייצוא

בהגדרת CFS, משלוח הוא הובלה יחידה של סחורות, מצרכים או מוצרים ממפעל ללקוח יחיד או למפעל אחר שבבעלותה או המופעל על ידי אותה חברה בהקמת המוצא (למשל מחסן, מרכז הפצה, או חנות קמעונאית או סיטונאית). משאיות מלאות או חלקיות נחשבו כמשלוח יחיד רק אם כל הסחורות במשאית נועדו לאותו מקום. למספר משלוחים בנתיב, הסחורה שנמסרה בכל תחנה נספרה כמשלוח אחד. תזכירים בין משרדים, המחאות שכר או התכתבות עסקית לא נכללו ב- CFS. כמו כן, ה- CFS אינו כולל משלוחי פסולת, נייר גרוטאות, פסולת או חומרים למחזור, אלא אם כן המפעל עסק במכירת או אספקת חומרים אלה.

למשלוח שכלל יותר ממצרך אחד, הונחה המשיבה לדווח על הסחורה שהייתה האחוז הגדול ביותר ממשקל המשלוח.

בנוסף, המפעלים התבקשו לספק מידע על השימוש והיקף של שירותי משלוחים.

שיטת איסוף נתונים

סקר ה- CFS נערך באמצעות דיוור אלקטרוני/דואר אלקטרוני עם אפשרות דיווח אלקטרונית. כל מפעל שנבחר במדגם ה- CFS לשנת 2012 נשלח בדואר לארבעה שאלונים-אחד במהלך כל רבעון קלנדרי של שנת 2012. ארבעת השאלונים היו זהים לכל תקופות הדיווח (ראה נספח ה להעתק של השאלון) . The establishments were asked to provide shipment information about a sample of their individual outbound shipments during a prespecified one-week period in each calendar quarter. Each of the 4 weeks was in the same relative position of the calendar quarter. Respondents had the option of reporting electronically and were given log-in information on their mailed questionnaire.

Mileage Calculations

The distance traveled by each freight shipment reported by the respondents to the 2012 CFS was estimated by a soft-ware tool called GeoMiler that uses routing algorithms and an integrated, intermodal transportation network that has been developed and updated expressly for this purpose. Each shipment record contained the ZIP Codes of shipment origin and destination (O-D pair) and the mode or modal sequence required by the routing algorithm for distance estimation. Each record also contained information on type of commodity moved, its weight, dollar value, and hazardous materials (hazmat) status. For each export ship-ment, the U.S. port of exit (POE) was also identified, along with foreign destination country a destination country of Canada/Mexico also required a Canadian/Mexican destina-tion city.

Valid and accurate O-D pair ZIP Codes were essential elements needed for estimating the travel distance of any shipment. For shipments with missing or invalid geographic data elements, such data elements were imputed, if a reasonable correction appeared obtainable (e.g., if a specific destination city/state was provided, then a “reasonably reliable” destination ZIP Code was imputed for the shipment). Follow-up contact with respondents was required when the missing information could not be reasonably imputed.

GeoMiler—Software to Measure the Distance Traveled by Commodity Shipments

The CFS does not ask respondents to report the distance traveled for each shipment. Therefore, shipment mileage was calculated using GeoMiler, a routing tool developed by BTS specifically for CFS mileage calculations. GeoMiler used current Geographic Information System (GIS) technology and spatial multimodal network databases and integrated map-visualization features with route solvers to handle many alternative multimodal combinations. This tool used algorithms that found the quickest path over spatial representations of the U.S. highway, railway, waterway, and airway networks. For waterborne export shipments, GeoMiler used a waterborne commerce database from the U.S. Army Corps of Engineers (USACE) to route freight originating in the United States via the deep sea (ocean). For airborne export shipments, GeoMiler used an updated air export network from the BTS Office of Airline Information (OAI).

Methodological Changes to Mileage Calculation for the 2012 CFS

With a valid origin and destination Zip Code, GeoMiler will calculate the distance traveled (in miles) by mode for each shipment reported in the CFS. The following types of methodological changes to mileage processing were incorporated in 2012:

  • A shipment with a respondent-provided mode of Parcel must weigh 150 pounds or less in addition, a shipment with a respondent-provided mode of Air was not given a weight restriction.
  • A mode of transportation was imputed whenever a respondent provided a mode of Other, or Unknown, or otherwise failed to provide a modal response (missing mode) for a shipment.
  • Private truck is considered a “short-haul” mode hence Private truck shipments were not routed more than 500 miles during shipment routing.

According to the 2007 CFS Instruction Guide, an Air shipment was defined as a shipment that weighed 100 pounds or more. During mileage processing for the 2007 CFS, an Air shipment was manually converted to Parcel if the weight of the shipment was less than 100 pounds.

However, airlines do not necessarily have minimum weight restrictions when transporting cargo. Hence, for the 2012 CFS, the definition of an Air shipment was changed. As a result, an Air shipment was acceptable as provided by the respondent, regardless of weight.

Furthermore, for the 2012 CFS, Parcel shipments conformed to the definition used by the parcel industry that a parcel is a shipment of 150 pounds or less. For shipments submitted by the respondent with mode of Parcel and a weight above 150 pounds, GeoMiler changed the mode to For-hire truck during mileage processing.

Routing a Shipment When Mode Is Other, Unknown, or Missing

On the survey form, respondents were given the following choices for mode of transport: Air, Highway (Private truck or For-hire truck), Rail, Waterway (Inland water or Deep sea), Parcel, Pipeline, Other mode (meaning none of the above), or Unknown.

During the 2007 CFS mileage processing, 2.4 percent of shipments had a respondent-provided mode of Unknown or Other, and an additional 2.1 percent had no reported mode at all. In these situations, the mode of transport was imputed. For 2012 CFS mileage processing, if the shipment weighed less than 80,000 pounds, it was routed via Highway mode as For-hire truck if the shipment weighed 80,000 pounds or more, it was routed via Rail mode.

Private Truck Versus For-Hire Truck

Shipments via Private truck are generally “short-haul” in nature. Because of the number of shipments exceeding this norm in the 2007 CFS, Census Bureau analysts researched the Private truck shipments at or above 500 miles. In almost all cases, the mode should have been reported as For-hire truck instead of Private truck.

Consequentially, for 2012 CFS GeoMiler mileage processing, Private truck was converted to For-hire truck if the shipment mileage was equal to or greater than 500 miles, regardless of the commodity being transported. The 2012 CFS preliminary data shows a decrease from 2007 in average miles per shipment for Private truck, with an average of 46 miles per shipment.

Mileage for Domestic Shipments

For a domestic shipment, the mileage was calculated between the centroid (center of a geographic area) of the U.S. origin ZIP Code and the centroid of the destination ZIP Code. The route between an O-D pair was composed of a series of links, and an impedance factor was assigned to each link (impedance is defined as a function of distance and travel time). Given a mode or modal sequence, the role of GeoMiler was to find that “best path” route which minimized the total impedance of the links between the specified O-D pair.

The mileage for shipments within a ZIP Code (matching O-D pair) was calculated by means of a formula that approximated the longest distance within the boundaries of that ZIP Code.

For multimodal shipments (those shipments involving more than one mode, such as truck-rail shipments), spatial joins (intermodal transfer links) were added to the network database to connect the individual modal networks together for routing purposes. An intermodal terminals database and a number of terminal transfer models were developed at BTS to identify likely transfer points for freight. An algorithm was used to find the minimum impedance path between a shipment’s origin ZIP Code to the transfer point and then from the transfer point to the destination ZIP Code. Thus, for multimodal shipments, the cumulative length of the spatial joins, plus links on the path, was used for estimating distances.

To estimate highway mileage, GeoMiler considered the functional class of highway so that the “single best path” was the quickest path based on the likely use of interstate and other major roadways and not necessarily the shortest path. The “quickest path” algorithms in terms of travel time incorporated the following hierarchical functional class of highway:

The model favored the selection of higher-order routes (interstate) rather than lower-order routes (state and county), which provided a more realistic path for freight movement via highway.

To estimate railway mileage, GeoMiler selected a “single best path” from those calibrated with route density information obtained from sampled rail waybills, assigned a specific railroad company at shipment origin, and considered ownership, trackage rights, and interlining (the transfer from one railroad company’s trackage network to that of another).

To estimate waterway mileage, GeoMiler selected a “single best path” from the USACE waterway network featuring dock-to-dock movements (from the dock nearest to origin, to the dock nearest to destination) by specific two-digit commodity codes for the Standard Classification of Transported Goods (SCTG).

To estimate domestic airway mileage, GeoMiler selected the “single best path” from the three airports closest to the origin ZIP Code to the three airports closest to the destination ZIP Code. Criteria for route selection were calibrated with air route information provided by the OAI at BTS. As in the past, to be acceptable, an airway routing must generate at least twice as many airway miles as highway miles (the ratio of air/truck miles should be at least 2 to 1) in order to reach the destination. Consequently, GeoMiler chose the most likely air route from those routes that were nonstop (direct) from airport facilities with higher cargo lifts (weight transported between two airports) based on the OAI air cargo data.

Mileage for Pipeline Shipments

For pipeline shipments, ton-miles and average miles per shipment are not shown in the data files. For most of these shipments, the respondents reported the shipment destination as a pipeline facility on the main pipeline network. Therefore, for the majority of these shipments, the resulting mileage represented only the access distance through feeder pipelines to the main pipeline network and not the actual distance through the main pipeline network. Pipeline shipments are included in the U.S. totals for ton-miles and average miles per shipment. For security purposes, there is no pipeline network available in the public domain with which to route petroleum-based products. Hence, any modal distance, either single or multi, involving pipeline was considered as solely pipeline mileage from origin ZIP Code to destination ZIP Code and calculated to equal great circle distance (GCD). GCD is defined as the shortest distance between two points on the earth’s surface, taking into account the earth’s curvature.

Mileage Routing in Alaska

Much of Alaska is inaccessible by any mode of transportation except “bush” airplanes. A “bush” airplane is a small aircraft that usually carries no more than four people, including the “bush” pilot. For the 2012 CFS, a network of mini airports, more extensive than that used previously in the 2007 CFS, was incorporated into intrastate travel within Alaska to accommodate “short-hop” flights where no established roads existed, especially in cases where the respondent reported a mode of highway.

Mileage for Export Shipments

For all exports, GeoMiler determined a U.S. port of exit (POE): seaport, airport, or border crossing (in the case of highway exports to the border countries of Canada/Mexico). However, only the portion of mileage measured within U.S. borders was included as domestic mileage in the CFS estimates for export shipments. To find the POE, GeoMiler used foreign destination country, type of commodity being exported, port volume (tonnage), and domestic travel distances.

The mileage estimates for export shipments in the 2012 CFS included the total distance from the shipment origin up to the exit point on the U.S. territorial borders.

For waterway exports via inland waterways (e.g., the Mississippi River), the mileage calculation included the distance from an inland water POE (such as St. Louis) to a coastal POE (such as New Orleans), and this extra inland waterway mileage was included in the total domestic mileage for this shipment.

For waterway exports via the Great Lakes (Lakes Erie, Huron, Michigan, Ontario, Superior), the mileage calculation was continued from a Great Lakes POE (such as Chicago, Cleveland, Duluth) to the line of demarcation between the United States and Canada (drawn within each of the Great Lakes except Michigan), and this extra Great Lakes mileage was included in the total domestic mileage for this shipment.


How to Use Traceroute

Traceroute is run from a command prompt or terminal window. On Windows, press the Windows key, type Command Prompt, and press Enter to launch one.

To run a traceroute, run the tracert command followed by the address of a website. For example, if you wanted to run a traceroute on How-To Geek, you’d run the command:

(On Mac or Linux, run traceroute howtogeek.com instead.)

You’ll gradually see the route take form as your computer receives responses from the routers along the way.

If you run a traceroute for another website – particularly one hosted in a different region of the world – you’d see how the paths differ. The first “hops” are the same as the traffic reaches your ISP, while the later hops are different as the packets go elsewhere. For example, below you can see the packets travelling to Baidu.com in China.


Distance Matrix responses

Responses to Distance Matrix API queries are returned in the format indicated by the output flag within the URL request's path.

Two sample HTTP requests are shown below, requesting distance and duration from Vancouver, BC, Canada and from Seattle, WA, USA, to San Francisco, CA, USA and to Victoria, BC, Canada.

This request demonstrates using the JSON output flag:

This request demonstrates using the XML output flag:

This request will return four elements - two origins times two destinations:

Vancouver to San Francisco Vancouver to Victoria
Seattle to San Francisco Seattle to Victoria

Results are returned in rows, each row containing one origin paired with each destination.

You can test this by entering the URL into your web browser (be sure to replace YOUR_API_KEY with your actual API key).

Select the tabs below to see the sample JSON and XML responses.

Note that these results generally need to be parsed if you wish to extract values from the results. Parsing JSON is relatively easy. See Parsing JSON for some recommended design patterns.

We recommend that you use json as the preferred output flag unless your service requires xml for some reason. Processing XML trees requires some care, so that you reference proper nodes and elements. See Parsing XML with XPath for some recommended design patterns for output processing.

The remainder of this documentation will use JSON syntax.

Distance Matrix response elements

Distance Matrix responses contain the following root elements:

  • status contains metadata on the request. See Status Codes below.
  • origin_addresses contains an array of addresses as returned by the API from your original request. These are formatted by the geocoder and localized according to the language parameter passed with the request.
  • destination_addresses contains an array of addresses as returned by the API from your original request. As with origin_addresses , these are localized if appropriate.
  • rows contains an array of elements , which in turn each contain a status , duration , and distance element.

Status codes

The status fields within the response object contain the status of the request, and may contain useful debugging information. The Distance Matrix API returns a top-level status field, with information about the request in general, as well as a status field for each element field, with information about that particular origin-destination pairing.

Top-level status codes

  • OK indicates the response contains a valid result .
  • INVALID_REQUEST indicates that the provided request was invalid.
  • MAX_ELEMENTS_EXCEEDED indicates that the product of origins and destinations exceeds the per-query limit.
  • MAX_DIMENSIONS_EXCEEDED indicates that the number of origins or destinations exceeds the per-query limit.
  • OVER_DAILY_LIMIT indicates any of the following:
    • The API key is missing or invalid.
    • Billing has not been enabled on your account.
    • A self-imposed usage cap has been exceeded.
    • The provided method of payment is no longer valid (for example, a credit card has expired).

    See the Maps FAQ to learn how to fix this.

    Element-level status codes

    • OK indicates the response contains a valid result .
    • NOT_FOUND indicates that the origin and/or destination of this pairing could not be geocoded.
    • ZERO_RESULTS indicates no route could be found between the origin and destination.
    • MAX_ROUTE_LENGTH_EXCEEDED indicates the requested route is too long and cannot be processed.

    Error messages

    When the top-level status code is other than OK , there may be an additional error_message field within the Distance Matrix response object. This field contains more detailed information about the reasons behind the given status code.

    הערה: This field is not guaranteed to be always present, and its content is subject to change.

    When the Distance Matrix API returns results, it places them within a JSON rows array. Even if no results are returned (such as when the origins and/or destinations don't exist), it still returns an empty array. XML responses consist of zero or more <row> elements.

    Rows are ordered according to the values in the origin parameter of the request. Each row corresponds to an origin, and each element within that row corresponds to a pairing of the origin with a destination value.

    Each row array contains one or more element entries, which in turn contain the information about a single origin-destination pairing.

    אלמנטים

    The information about each origin-destination pairing is returned in an element entry. An element contains the following fields:

    • status : See Status Codes for a list of possible status codes.
    • duration : The length of time it takes to travel this route, expressed in seconds (the value field) and as text . The textual representation is localized according to the query's language parameter.

    duration_in_traffic : The length of time it takes to travel this route, based on current and historical traffic conditions. See the traffic_model request parameter for the options you can use to request that the returned value is optimistic, pessimistic, or a best-guess estimate. The duration is expressed in seconds (the value field) and as text . The textual representation is localized according to the query's language parameter. The duration in traffic is returned only if all of the following are true:

    • The request includes a departure_time parameter.
    • The request includes a valid API key, or a valid Google Maps Platform Premium Plan client ID and signature.
    • Traffic conditions are available for the requested route.
    • The mode parameter is set to driving .
    • currency : An ISO 4217 currency code indicating the currency that the amount is expressed in.
    • value : The total fare amount, in the currency specified above.
    • text : The total fare amount, formatted in the requested language.

    Below is an example of an element containing fare information:


    2 תשובות 2

    As the hint suggested, to reach $(5,5)$ from $(0,0)$, we will take $10$ consecutive "steps," of which $5$ will be up and $5$ to the right. We can בחר any $5$ of these $10$ steps to be the "up" steps.

    So there are $inom<10><5>$ possible paths.

    To visualize the problem draw the quarter xy plane, that is, the positive x and y axises, on a graphing sheet. Now mark all the points with integer coordinates on and inside the square whose vertices are (0,0),(0,5),(5,0), and (5,5). You can draw small dots to make these marks. So, for example, you would have a dot on your graphing paper at the point (1,1). When you are done, you should have a total of 25 points. Now, the question asks, how many ways are there, starting from the origin (0,0), to move to the corner point (5,5), with the constraint that you can only move up or right and you can only step on the drawn points? A sample path would be (0,1)(0,2)(1,2)(2,2)(3,2)(3,3)(3,4)(4,4)(5,4)(5,5). Notice that you can't move diagonally to a point. Only up and right. Obviously you can count all the distinct paths by actually drawing them out or you can use combinatorics and counting methods to compute the number of paths.


    I've created an example file for you: get driving distance

    where A2 is the origin and B2 is the destination.

    You have to get an API key from mapquest and replace the value YOUR_KEY_HERE with it.

    This is what works for me:

    This will yield the driven distance between <point.A> and <point.B> in meters (according to Google Maps, of course).

    I do not think there is built in Excel function, or extension, to do this.

    You might want to check out this Source Forge page: http://zips.sourceforge.net/

    • It provides a CSV dataset to convert Zip Codes to Lat/Long (center point presumably)
    • It provides Excel code to calculate the "crow flies" distance between two lat/long coordinates. (and includes equivalent code for Java, PHP and Python.

    The page notes that the angles have to be in Radians and that Excel has a degrees to Radians conversion function:

    Unless someone else has a slicker answer, this should get you what you want without too much work.

    For a complete Google spreadsheet example, in the form of a spreadsheet template, plus information about the Google Maps API: http://winfred.vankuijk.net/2010/12/calculate-distance-in-google-spreadsheet/

    Google Developers offers a very robust script for map related functions in Google Sheets that I used and have really enjoyed. Full instructions are on the webpage as well.

    I am not familiar enough with the APIs to tell you exactly how to do this, but I would think it would be possible using the Google Maps API.

    Google Maps, of course, can provide directions from one point to another through their API. It would be complicated, but possible to route the locations from the spreadsheet through the API and get driving directions, which would give you a driving distance between cities.

    You can write the functions on your own which is similar like macro's

    you can find the full document here

    PS: Currently It doesn't open for all Google Apps Script