[發(fā)明專利]拼車路線的確定方法及裝置、存儲介質(zhì)、計算設(shè)備

有效

• 申請?zhí)枺?/td>: 201810942911.4
• 申請日: 2018-08-17
• 公開（公告）號: CN109118006B
• 公開（公告）日: 2021-05-28
• 發(fā)明（設(shè)計）人: 金忠孝;管揚
• 申請（專利權(quán)）人: 安吉汽車物流股份有限公司;上海汽車集團股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30
• 代理公司: 北京信遠達知識產(chǎn)權(quán)代理有限公司 11304
• 代理人: 魏曉波

1.一種拼車路線的確定方法，其特征在于，包括：

確定拼車路線的出發(fā)地與各個目標(biāo)地之間產(chǎn)生的距離代價，并確定各個目標(biāo)地彼此之間產(chǎn)生的距離代價；

確定所述出發(fā)地至每一目標(biāo)地產(chǎn)生的訂單交付代價，并確定各個目標(biāo)地彼此之間產(chǎn)生的訂單交付代價；

分別將每一目標(biāo)地作為各個拼車路線的終點保存至動態(tài)規(guī)劃表中，基于所述動態(tài)規(guī)劃表、所述出發(fā)地距離各個目標(biāo)地產(chǎn)生的距離代價、各個目標(biāo)地彼此之間產(chǎn)生的距離代價，以及所述出發(fā)地至每一目標(biāo)地產(chǎn)生的訂單交付代價、各個目標(biāo)地彼此之間產(chǎn)生的訂單交付代價，利用動態(tài)規(guī)劃算法確定各個拼車路線各自的總代價；

將各個拼車路線中總代價最小的拼車路線確定為從所述出發(fā)地經(jīng)各個目標(biāo)地形成的拼車路線；

其中，所述確定從所述出發(fā)地至每一目標(biāo)地產(chǎn)生的訂單交付代價包括：確定所述出發(fā)地產(chǎn)生的出廠訂單交付代價；確定從所述出發(fā)地至每一目標(biāo)地的運輸過程中各自產(chǎn)生的路程訂單交付代價；將所述出廠訂單交付代價與每一目標(biāo)地對應(yīng)的路程訂單交付代價之和確定為從所述出發(fā)地至該目標(biāo)地產(chǎn)生的訂單交付代價；確定各個目標(biāo)地彼此之間產(chǎn)生的訂單交付代價包括：確定各個目標(biāo)地彼此之間產(chǎn)生的路程訂單交付代價；

所述基于所述出發(fā)地與各個目標(biāo)地之間產(chǎn)生的距離代價、各個目標(biāo)地彼此之間產(chǎn)生的距離代價，以及從所述出發(fā)地至每一目標(biāo)地產(chǎn)生的訂單交付代價、各個目標(biāo)地之間產(chǎn)生的訂單交付代價，利用動態(tài)規(guī)劃算法確定各個拼車路線各自的代價包括：

在第1階段，對于每一拼車路線，在該拼車路線中分別加入各自剩余的目標(biāo)地以得到各個子路線的當(dāng)前起點，將各個子路線的當(dāng)前起點與所述終點之間產(chǎn)生的訂單交付代價以及距離代價之和確定為所述第1階段各個子路線各自的代價，并將各個子路線存儲至所述動態(tài)規(guī)劃表中，所述剩余的目標(biāo)地是終點以外的目標(biāo)地，所述子路線是終點和所述剩余的目標(biāo)地形成的路線；

在第k階段，對于每一拼車路線，如果未加入所有目標(biāo)地和所述出發(fā)地，那么對于該拼車路線的每一子路線，分別將未加入該子路線的其余目標(biāo)地和所述出發(fā)地確定為該子路線的新起點，基于各個目標(biāo)地彼此之間產(chǎn)生的訂單交付代價和距離代價，或者基于所述出發(fā)地至每一目標(biāo)地產(chǎn)生的訂單交付代價和距離代價，確定第(k-1)階段至第k階段的新增代價，并將該子路線的新增代價與第(k-1)階段的代價之和的最小值確定為該拼車路線在第k階段的代價，更新該拼車路線至所述動態(tài)規(guī)劃表中，直至加入所有目標(biāo)地和所述出發(fā)地為止，k≥2且k為正整數(shù)；

其中，所述基于各個目標(biāo)地彼此之間產(chǎn)生的訂單交付代價和距離代價，或者基于所述出發(fā)地至每一目標(biāo)地各自產(chǎn)生的訂單交付代價和距離代價，確定第(k-1)階段至第k階段的新增代價包括：

對于每一拼車路線，確定該拼車路線剩余目標(biāo)地及所述出發(fā)地的總數(shù)；

如果未加入所述拼車路線的剩余目標(biāo)地及所述出發(fā)地的總數(shù)小于預(yù)設(shè)閾值，則基于各個目標(biāo)地彼此之間產(chǎn)生的訂單交付代價和距離代價，或者基于所述出發(fā)地至每一目標(biāo)地各自產(chǎn)生的訂單交付代價和距離代價，確定基本代價，否則確定加急代價；

將所述基本代價或加急代價確定為所述第(k-1)階段至所述第k階段的新增代價；

所述基本代價采用如下公式表示：r_sj＝D_sj+OTD(s,j),N-km，或者，r_ij＝D_ij+OTD(i,j),N-km，所述加急代價采用如下公式表示：r’_sj＝D_sj+2·OTD(s,j),N-k≥m，或者，r’_ij＝D_ij+2·OTD(i,j),N-k≥m；

其中，r_sj表示出發(fā)地s與目標(biāo)地j之間產(chǎn)生的基本代價、r’_sj表示出發(fā)地s與目標(biāo)地j之間產(chǎn)生的加急代價，r_ij表示目標(biāo)地i與目標(biāo)地j之間產(chǎn)生的基本代價，r’_ij表示目標(biāo)地i與目標(biāo)地j之間產(chǎn)生的加急代價，D_sj表示出發(fā)地s與目標(biāo)地j之間產(chǎn)生的距離代價，D_ij表示目標(biāo)地i與目標(biāo)地j之間產(chǎn)生的距離代價；OTD(s,j)表示出發(fā)地s與目標(biāo)地j之間產(chǎn)生的訂單交付代價，OTD(i,j)表示目標(biāo)地i與目標(biāo)地j之間產(chǎn)生的訂單交付代價；(N-k)表示所述剩余目標(biāo)地及所述出發(fā)地的總數(shù)，N表示所述出發(fā)地和所有目標(biāo)地的全部數(shù)量；m表示所述預(yù)設(shè)閾值。