[發(fā)明專利]在公共運(yùn)輸網(wǎng)絡(luò)中的旅行規(guī)劃

在審

• 申請(qǐng)?zhí)枺?/td>: 201210328078.7
• 申請(qǐng)日: 2012-09-06
• 公開(kāi)（公告）號(hào): CN102915401A
• 公開(kāi)（公告）日: 2013-02-06
• 發(fā)明（設(shè)計(jì)）人: D·德林;A·V·戈德伯格;T·帕約爾;R·F·韋爾內(nèi)克
• 申請(qǐng)（專利權(quán)）人: 微軟公司
• 主分類號(hào): G06F19/00
• 分類號(hào): G06F19/00
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 顧嘉運(yùn)

1.一種確定在公共運(yùn)輸網(wǎng)絡(luò)中的兩個(gè)位置之間的旅行的方法，包括：

在計(jì)算設(shè)備處接收數(shù)據(jù)結(jié)構(gòu)作為輸入，所述數(shù)據(jù)結(jié)構(gòu)表示所述公共運(yùn)輸網(wǎng)絡(luò)并且包括分組為路線的多個(gè)站點(diǎn)和旅程；

由所述計(jì)算設(shè)備執(zhí)行在所述多個(gè)站點(diǎn)的第一站點(diǎn)和所述多個(gè)站點(diǎn)的第二站點(diǎn)之間的Pareto最佳旅行計(jì)算，其中所述第一站點(diǎn)是源位置而所述第二站點(diǎn)是目的地位置，并且其中所述Pareto最佳旅行計(jì)算受限于最小化旅行時(shí)間和最小化換乘次數(shù)的條件；

如果Pareto最佳旅行存在，則通過(guò)所述計(jì)算設(shè)備輸出所述源位置和所述目的地位置之間的至少一個(gè)Pareto最佳旅行。

2.如權(quán)利要求1所述的方法，其特征在于，執(zhí)行在所述第一站點(diǎn)和所述第二站點(diǎn)之間的Pareto最佳旅行計(jì)算包括對(duì)所述網(wǎng)絡(luò)執(zhí)行多個(gè)循環(huán)，所述多個(gè)循環(huán)的每個(gè)循環(huán)確定從所述網(wǎng)絡(luò)上的第一站點(diǎn)到使用預(yù)定數(shù)目的旅程可到達(dá)的每個(gè)其它站點(diǎn)的最佳旅行。

3.如權(quán)利要求2所述的方法，其特征在于，進(jìn)一步包括接收表示旅程的最大數(shù)目的整數(shù)，其中所述多個(gè)循環(huán)是基于所述表示所述旅程的最大數(shù)目的整數(shù)，而每個(gè)循環(huán)對(duì)應(yīng)于不大于所述旅程的最大數(shù)目的一個(gè)不同數(shù)目。

4.如權(quán)利要求3所述的方法，其特征在于，每個(gè)循環(huán)的旅程的預(yù)定數(shù)目等于所述對(duì)應(yīng)于每個(gè)循環(huán)的不同數(shù)目。

5.如權(quán)利要求2所述的方法，其特征在于，執(zhí)行每個(gè)循環(huán)包括：

確定對(duì)應(yīng)于在所述網(wǎng)絡(luò)上使用所述預(yù)定數(shù)目的旅程可到達(dá)的站點(diǎn)的每個(gè)運(yùn)輸站點(diǎn)的到達(dá)時(shí)間；以及

為每個(gè)可到達(dá)的站點(diǎn)用最早的確定的到達(dá)時(shí)間設(shè)置一個(gè)標(biāo)簽。

6.如權(quán)利要求2所述的方法，其特征在于，還包括在執(zhí)行所述Pareto最佳旅行計(jì)算之前在所述計(jì)算設(shè)備處接收查詢，其中所述查詢標(biāo)識(shí)了所述源位置、所述目的地位置和出發(fā)時(shí)間。

7.如權(quán)利要求1所述的方法，其特征在于，執(zhí)行在所述第一站點(diǎn)和所述第二站點(diǎn)之間的所述Pareto最佳旅行計(jì)算包括對(duì)所述網(wǎng)絡(luò)執(zhí)行多個(gè)循環(huán)，其中所述多個(gè)循環(huán)的每個(gè)循環(huán)在使用預(yù)定數(shù)目的換乘可到達(dá)的多個(gè)旅程上進(jìn)行迭代。

8.如權(quán)利要求1所述的方法，其特征在于，執(zhí)行在所述第一站點(diǎn)和所述第二站點(diǎn)之間的所述Pareto最佳旅行計(jì)算包括對(duì)所述網(wǎng)絡(luò)執(zhí)行多個(gè)循環(huán)，其中所述多個(gè)循環(huán)的每個(gè)循環(huán)在使用預(yù)定數(shù)目的換乘可到達(dá)的多個(gè)路線上進(jìn)行迭代。

9.如權(quán)利要求8所述的方法，其特征在于，還包括通過(guò)僅遍歷前次循環(huán)到達(dá)的路線來(lái)限制在每個(gè)循環(huán)中所迭代的路線。

10.如權(quán)利要求1所述的方法，其特征在于，在所述源位置和所述目的地位置之間的至少一個(gè)Pareto最佳旅行包括在所述旅行中所執(zhí)行的換乘總數(shù)少于預(yù)定數(shù)目的最早可能的到達(dá)時(shí)間。