Abstract
This paper is the first attempt to propose an efficient auction mechanism for the regional logistics synchronization (RLS) problem, which aims to capture both logistics punctuality and simultaneity in a regional logistics network. The main motivation of RLS is motivated by our industrial collaborator, i.e. a third-party logistics (3PL) company, that if the delay has already occurred or will occur, the customers tend to pursue the simultaneity. We develop the one-sided Vickrey–Clarke–Groves (O-VCG) auction to realize incentive compatibility (on the buy side), budget balance, and individual rationality. The vehicle routing problem faced by the 3PL company is formulated as the lane covering problem with RLS requirements. Given the complexity of the proposed model, three canonical swarm intelligence meta-heuristics are employed to address the auction-based RLS problem. Besides, a superior tracking artificial bee colony with novel information learning mechanism is further developed to explore better solutions. Comparison results reveal the effectiveness of the proposed optimizers in terms of realized social welfare. Experimental results show that the O-VCG auction can achieve high synchronization level, approximately allocative efficiency and (ex post) budget balance.
Similar content being viewed by others
References
Akay, B., & Karaboga, D. (2009). Parameter tuning for the artificial bee colony algorithm. In First international conference of computational collective intelligence. Semantic web, social networks and multiagent systems pp. 608–619.
Belmecheri, F., Prins, C., Yalaoui, F., & Amodeo, L. (2013). Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows. Journal of Intelligent Manufacturing, 24(4), 775–789.
Bratton, D., & Kennedy, J. (2007). Defining a standard for particle swarm optimization. In Proceedings of the 2007 IEEE swarm intelligence symposium pp. 120–127.
Chen, J. X., Liu, Z. Y., Zhu, S. L., & Wang, W. (2015a). Design of limited-stop bus service with capacity constraint and stochastic travel time. Transportation Research Part E-Logistics and Transportation Review, 83, 1–15.
Chen, J., Huang, G. Q., Luo, H., & Wang, J. (2015b). Synchronisation of production scheduling and shipment in an assembly flowshop. International Journal of Production Research, 53(9), 2787–2802.
Chen, R. L. Y., AhmadBeygi, S., Cohn, A., Beil, D. R., & Sinha, A. (2009). Solving truckload procurement auctions over an exponential number of bundles. Transportation Science, 43(4), 493–510.
Chu, X., Hu, G., Niu, B., Li, L., & Chu, Z. (2016a). An superior tracking artificial bee colony for global optimization problems. In IEEE congress on evolutionary computation pp. 2712–2717.
Chu, X., Hu, M., Wu, T., Weir, J. D., & Lu, Q. (2014). AHPS\(\wedge \)2: An optimizer using adaptive heterogeneous particle swarms. Information Sciences, 280, 26–52.
Chu, X., Niu, B., Liang, J. J., & Lu, Q. (2016b). An orthogonal-design hybrid particle swarm optimiser with application to capacitated facility location problem. International Journal of Bio-Inspired Computation, 8, 268–285.
Clerc, M., & Kennedy, J. (2002). The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58–73.
Clarke, E. H. (1971). Multipart pricing of public goods. Public Choice, 11(1), 17–33.
De, A., Mamanduru, V. K. R., Gunasekaran, A., Subramanian, N., & Tiwari, M. K. (2016). Composite particle algorithm for sustainable integrated dynamic ship routing and scheduling optimization. Computers and Industrial Engineering, 96, 201–215.
De, A., Kumar, S. K., Gunasekaran, A., & Tiwari, M. K. (2017). Sustainable maritime inventory routing problem with time window constraints. Engineering Applications of Artificial Intelligence, 61, 77–95.
Dechampai, D., Tanwanichkul, L., Sethanan, K., & Pitakaso, R. (2017). A differential evolution algorithm for the capacitated VRP with flexibility of mixing pickup and delivery services and the maximum duration of a route in poultry industry. Journal of Intelligent Manufacturing, 28(6), 1357–1376.
Dou, R., Zong, C., & Nan, G. (2016). Multi-stage interactive genetic algorithm for collaborative product customization. Knowledge-Based Systems, 92, 43–54.
Dou, R., Zhang, Y., & Nan, G. (2017). Iterative product design through group opinion evolution. International Journal of Production Research, 55(13), 3886–3905.
Drexl, M. (2012). Synchronization in vehicle routing: A survey of VRPs with multiple synchronization constraints. Transportation Science, 46(3), 297–316.
Eberhart, R., & Kennedy, J. (1995). A new optimizer using particle swarm theory. In Sixth international symposium on micro machine and human science pp. 39–43.
El-Sherbeny, N. A. (2010). Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University-Science, 22, 123–131.
Ergun, Ö., Kuyzu, G., & Savelsbergh, M. (2007). Reducing truckload transportation costs through collaboration. Transportation Science, 41(2), 206–221.
Figliozzi, M. A. (2006). Analysis and evaluation of incentive-compatible dynamic mechanisms for carrier collaboration. Transportation Research Record, 1966, 34–40.
Figliozzi, M. A., Mahmassani, H. S., & Jaillet, P. (2007). Pricing in dynamic vehicle routing problems. Transportation Science, 41(3), 302–318.
Groves, T. (1973). Incentives in teams. Econometrica, 41(4), 617–631.
Hong, P. N., & Ahn, C. W. (2016). Fast artificial bee colony and its application to stereo correspondence. Expert Systems with Applications, 45, 460–470.
Jadon, S. S., Tiwari, R., Sharma, H., & Bansal, J. C. (2017). Hybrid artificial bee colony algorithm with differential evolution. Applied Soft Computing, 58, 11–24.
Karaboga, D., & Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3), 459–471.
Karaboga, D., Gorkemli, B., Ozturk, C., & Karaboga, N. (2014). A comprehensive survey: Artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review, 42(1), 21–57.
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In IEEE international conference on neural networks pp. 1942–1948.
Kennedy, J., & Mendes, R. (2002). Population structure and particle swarm performance. In Proceedings of the 2002 congress on evolutionary computation pp. 1671–1676.
Krishna, V. (2009). Auction Theory (2nd ed.). Cambridge: Academic Press.
Leung, S. C. H., Zhang, Z. Z., Zhang, D. F., Hua, X., & Lim, M. K. (2013). A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints. European Journal of Operational Research, 225(2), 199–210.
Liang, J. J., Qin, A. K., Suganthan, P. N., & Baskar, S. (2006). Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 10(3), 281–295.
Ning, Y. F., & Su, T. Y. (2017). A multilevel approach for modelling vehicle routing problem with uncertain travelling time. Journal of Intelligent Manufacturing, 28(3), 683–688.
Nisan, N., & Ronen, A. (2007). Computationally feasible VCG mechanisms. Journal of Artificial Intelligence Research, 29, 19–47.
Pureza, V., Morabito, R., & Reimann, M. (2012). Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW. European Journal of Operational Research, 218(3), 636–647.
Qin, Q., Cheng, S., Chu, X., Lei, X., & Shi, Y. (2017). Solving non-convex/non-smooth economic load dispatch problems via an enhanced particle swarm optimization. Applied Soft Computing, 59, 229–242.
Rosenthal, E. C., & Eisenstein, E. M. (2016). A rescheduling and cost allocation mechanism for delayed arrivals. Computers and Operations Research, 66, 20–28.
Shi, Y., & Eberhart, R. (1998). Modified particle swarm optimizer. In IEEE World Congress on Computational Intelligence pp. 69–73.
Song, J., & Regan, A. (2005). Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts. Transportation Research Part B, 39(10), 914–933.
Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1), 8–37.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). Heuristics for multiattribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 231(1), 1–21.
Wellman, M. P., Walsh, W. E., Wurman, P. R., & MacKie-Mason, J. K. (2001). Auction protocols for decentralized scheduling. Games and Economic Behavior, 35(1–2), 271–303.
Xu, S. X., & Huang, G. Q. (2014). Efficient auctions for distributed transportation procurement. Transportation Research Part B, 65, 47–64.
Xu, S. X., & Huang, G. Q. (2015). Auction-based transportation procurement in make-to-order systems. IIE Transactions, 47(11), 1236–1251.
Xu, S. X., & Huang, G. Q. (2017). Efficient multi-attribute multi-unit auctions for B2B e-commerce logistics. Production and Operations Management, 26(2), 292–304.
Xu, S. X., Huang, G. Q., & Cheng, M. (2016). Truthful, budget-balanced bundle double auctions for carrier collaboration. Transportation Science. https://doi.org/10.1287/trsc.2016.0694.
Yamada, T., & Febri, Z. (2015). Freight transport network design using particle swarm optimisation in supply chain-transport supernetwork equilibrium. Transportation Research Part E-Logistics and Transportation Review, 75, 164–187.
Zhang, S. Z., Lee, C. K. M., Choy, K. L., Ho, W., & Ip, W. H. (2014). Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem. Transportation Research Part D, 31, 85–99.
Acknowledgements
This work is partly supported by National Natural Science Foundation of China (Nos. 71501132, 71701079, 71521002 and 71402103), Natural Science Foundation of Guangdong Province (Nos. 2016A030310067 and 2015A030313556), and the 2016 Tencent “Rhinoceros Birds”— Scientific Research Foundation for Young Teachers of Shenzhen University. The second author and the third author contribute to this work equally.
Author information
Authors and Affiliations
Corresponding author
Appendix A
Appendix A
Proof of Theorem 1
It suffices to prove for the case of \(u_{3PL} >0\). Suppose that agents in \(I\backslash \{i\}\) bid truthfully. If agent i bids truthfully, then he makes a VCG-like payment, \(p_i (t_i )=v_i (t_i )-(\mathrm{Z}(I)-\mathrm{Z}(I\backslash i))\) (note: \(t_i \) can be empty), where
Similarly, if he bids \(\hat{{v}}_i (t)\), then he makes the corresponding VCG-like payment, \(\hat{{p}}_i (\hat{{t}}_i )=\hat{{v}}_i (\hat{{t}}_i )-(\hat{{\mathrm{Z}}}(I)-\mathrm{Z}(I\backslash i))\), where
If truthful bidding is not a dominant strategy for agent i, then
The above inequality can be rewritten as
which contradicts the fact that \(\varphi \) is an efficient allocation achieving \(\mathrm{Z}(I)\). \(\square \)
Proof of Theorem 2
It is clear that \(u_i (t_i )=\mathrm{Z}(I)-\mathrm{Z}(I\backslash i)\ge 0\). Thus, O-VCG auction is individually rational for each agent \(i\in I\). Since the 3PL company is the auctioneer, the trade will fail if \(u_{3PL} \le 0\). Also, the O-VCG auction is budget-balanced for the auctioneer. Based on Theorem 1 and the assumption that the 3PL company tells the truth, O-VCG auction finds an allocatively efficient allocation that maximizes social welfare. \(\square \)
Rights and permissions
About this article
Cite this article
Chu, X., Xu, S.X., Cai, F. et al. An efficient auction mechanism for regional logistics synchronization. J Intell Manuf 30, 2715–2731 (2019). https://doi.org/10.1007/s10845-018-1410-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-018-1410-2