近年來電子商務演變及發展快速，線上購物風行，大量的小型貨物和運送宅配作業必須快速地於都會區中及時運送，已逐漸變成城市物流必須面對的重大挑戰。這些小包裹物流配送問題實為一個「最初與最終一哩收送問題」，其運送流程中遇到的最大困難在於顧客經常無法在物流人員抵達時在場收送件，因而導致物流人員可能要多次造訪而提高了物流成本。因應此困難，本論文提出一個嶄新的收送機制：透過於高交通流量區域設置智能櫃，除可方便顧客依其方便之時刻自行前往智能櫃收送件外，更可讓智能櫃擔任多段接力配送的最佳「轉運點」；亦即可將某些貨物分段運送，每段皆以智能櫃當轉運或收送點，供不同的運送人員以接力方式將貨物輾轉收送。智能櫃之轉運功能至今為止雖仍未見於文獻或實務場域中，然而我們認為該功能可與近年來逐漸風行的眾包運送機制結合，讓物流公司支付一些在外通勤的眾包司機，鼓勵其利用閒置時間與車內空間來協助收送貨，讓其在原先個人的途程規劃中順道協助收送件，以降低整體運輸成本與人力負擔，此種機制將可減少人力與無效的配送，應可有效地處理原先城市物流中因難的最初與最終一哩收送問題。
在本研究中，我們針對此種多段接力或收送過程中所必須處理的司機匹配問題(multi-hop rider matching problem) ，建構兩種整數線性規劃模型：以節線為基礎的數學模型(Arc-Based model)，以及時空網路模型(Time-Space Network model)。兩者皆已考量節點上的智能櫃轉運可能性，選取合適的眾包司機，並以最小的額外繞路成本完成所有收送任務為目標。由於這些數學規劃模式之求解過程相當耗時，為了加速求解過程，我們提出了一種傾向直送方式的貪婪式演算法(Greedy algorithm)；此外，再提出一個滾動式時窗演算法(Rolling horizon algorithm)，先將整體的規劃期間離散化，切割成多個較小的求解時段，再依序求解之。在進行數學模式及演算法之數值測試後，我們發現貪婪式演算法的求解效果雖較差，但其初始解可被用亦幫助縮短整數規劃模型的求解時間，且此種方法僅能求解中等規模的網路圖；反之，滾動式時窗演算法因為每回合僅求解當下及較近的未來時段內之最佳運送規劃，不用一次將全天的時段列入考慮，因此針對更大規模的網路亦可有不錯的求解表現。

As e-commerce grows and evolves, a large volume of small freights and home deliveries need to be handled every day in city logistics. A major challenging city logistics management problem for the couriers is to deal with failed parcel collection or deliveries. This is the “first and last mile delivery problem” and may very likely lead to multiple ineffective receiving and delivery attempts with high logistics costs. Here we propose a new shipping framework that utilizes pickup and delivery via smart lockers typically located in high traffic areas. This network of smart lockers can serve as convenient access points to remedy the first and last mile delivery problem.
In addition to serving the purpose for directly delivering or receiving goods, smart lockers can also be used for transhipment, which in fact has almost been ignored in literature and in practice. This function of transhipment will be very useful for crowdshipping companies, since thousands of crowdsourced drivers are commuting between home and businesses with spare space in their cars, in order to reduce shipping costs and effort, shipping companies are also considering paying these independent drivers to deliver parcels for them on the way to their destinations.
In this research, we investigate the multi-hop rider matching problem which takes the transhipment on nodes of smart lockers into consideration. The objective of this problem is to minimize the total cost of delivering all the parcels under consideration on time. We proposed two integer linear programming models: the Arc-based model, and the Time-space network model. Since these mathematical programming models are too time-consuming, we propose a greedy algorithm focusing more on better directing shipping. We also provide a rolling horizon algorithm to split the planning horizon into multiple smaller time periods and solve them sequentially. From our computational experiments the results indicate that the initial solution obtained by our greedy algorithm does help to shorten the solution time of the integer programming models to some extent for solving cases of medium scale, and the rolling horizon algorithm can help solve networks of larger scale in a shorter time.

Agatz, N., Erera, A., Savelsbergh, M., Wang, X. (2010). Sustainable passenger transportation: Dynamic ride-sharing.
Agatz, N., Erera, A., Savelsbergh, M., Wang, X. (2011). Dynamic ride-sharing: a simulation study in metro Atlanta. Transportation Research Part B, 45(9), 1450-1464.
Agatz, N., Erera, A., Savelsbergh, M., Wang, X. (2012). Optimization for dynamic ride-sharing: a review. European Journal of Operational Research, 223(2), 295-303.
Baldacci, R., Maniezzo, V., Mingozzi, A. (2004). An exact method for the carpooling problem based on lagrangean column generation. Operations Research, 52(3), 422-439.
Chen, W., Mes, M., Schutten, M. (2017). Multi-hop driver-parcel matching problem with time windows. Flexible services and manufacturing journal, 1-37.
Coltin, B., Veloso, M. (2014). Ridesharing with passenger transfers. In Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp 3278-3283.
Cordeau, J., Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153 (1), 29-46.
Cortés, C., Matamala, M., Contardo, C. (2010). The pickup and delivery problem with transfers: formulation and a branch-and-cut solution method. European Journal of Operational Research, 200 (3) 711-724.
Deutsch, Y., Golany, B. (2017). A parcel locker network as a solution to the logistics last mile problem. International Journal of Production Research, 56:1-2, 251-261.
Faugere, L., Montreuil, B. (2016). Hyperconnected City Logistics: Smart Lockers Terminals and Last Mile Delivery Networks. In Proceedings of 3rd International Physical Internet Conference.
Faugere, L., Montreuil, B. (2017), Hyperconnected pickup and delivery locker networks. In Proceedings of the 4th International Physical Internet Conference.
Furuhata, M., Dessouky, M., Ordóñez, F., Brunet, M.-E., Wang, X., Koenig, S. (2013). Ridesharing: the state-of-the-art and future directions. Transportation Research Part B, 57, 28-46.
Herbawi,W., Weber,M. (2011a). Evolutionary multiobjective route planning in dynamic multi-hop ridesharing. European conference on evolutionary computation in combinatorial optimization, pp 84-95.
Herbawi, W., Weber, M. (2011b). Comparison of multiobjective evolutionary algorithm for solving the multiobjective route planning in dynamic multi-hop ridesharing. In: Proceedings of the 11th European Conference on Evolutionary Computation in Combinatorial Optimization, pp 84-95.
Herbawi, W., Weber, M. (2012). A genetic and insertion heuristic algorithm for solving the dynamic ridematching problem with time windows. In Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference, pp 385-392.
Hosni, H., Naoum-Sawaya, J., Artail, H. (2014). The shared-taxi problem: formulation and solution methods. Transportation Research Part B, 70, 303-318.
Kämäräinen, V. (2001). The Reception Box Impact on Home Delivery Efficiency in the E-Grocery Business. International Journal of Physical Distribution & Logistics Management, 31 (6), 414-426.
Lemke, J., S. Iwan, and J. Korczak (2016). Usability of the Parcel Lockers from the Customer Perspective: The Research in Polish Cities. Transportation Research Procedia, 16: 272-287.
Liaw, C.-F., White, C.C., Bander, J. (1996). A decision support system for the bimodal dial-a-ride problem. Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 26 (5), 552-565.
Masson, R., Lehuédé, F., Péton, O. (2014). The dial-a-ride problem with transfers. Computers & Operations Research, 41(0), 12-23.
Masson, R., Trentini, A., Lehuédé, F., Malhéné, N., Péton, O., Tlahig, H. (2015). Optimization of a city logistics transportation system with mixed passengers and goods. EURO Journal on Transportation and Logistics. 1-29.
Montreuil, B., R. D. Meller, and E. Ballot (2010). Towards a Physical Internet: The Impact on Logistics Facilities and Material Handling Systems Design and Innovation. Progress in Material Handling Research. 305-327.
Pitney Bowes Parcel Shipping Index forecasts 20 percent industry growth by 2018. (2018, October 16). Retrieved from https://www.pitneybowes.com/us/shipping-and-mailing /case -studies/pitney-bowes-2017-parcel-shipping-index.html
Punakivi, M., and Yrjölä H., Holmström J. (2001). Solving the Last Mile Issue: Reception Box or Delivery Box?. International Journal of Physical Distribution & Logistics Management, 31 (6), 427-439.
Savelsbergh, M.W.P., Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29 (1), 17-29.
Stein, D.M. (1978). Scheduling Dial-a-Ride Transportation Systems. Transportation Science 12 (3), 232-249.
Stiglic, M., Agatz, N., Savelsbergh, M., Gradisar, M. (2015). The Benefits of Meeting Points in Ride-Sharing Systems. Transportation Research Part B, 82, 36-53.
Wolfler Calvo, R., de Luigi, F., Haastrup, P., Maniezzo, V. (2004). A distributed geographic information system for the daily carpooling problem. Computers & Operations Research, 31 (13), 2263-2278.