Lane covering with partner bounds in collaborative truckload transportation procurement. (English) Zbl 1391.90069
Summary: In collaborative truckload transportation procurement, the collaborating shippers aim to jointly identify and submit tours with little or no asset repositioning to a carrier, as opposed to submitting individual lanes, in return for more favorable rates. In order to maximize savings, the shippers must solve a Lane Covering Problem (LCP), which in more mathematical terms means to cover a subset of arcs in a directed graph by a set of constrained cycles with minimum total cost. Previous works in the literature have proposed effective greedy algorithms or the solution of the NP-Hard LCP variants. This paper incorporates a new constraint into the LCP, motivated by the need to limit the number of partners with whom the collaborative tours must be coordinated. An integer programming model is formulated, and column generation and branch-and-price approaches are developed for the solution of the resulting LCP variant.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 90C35 | Programming involving graphs or networks |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 05C38 | Paths and cycles |
References:
| [1] | Amaldi, E.; Iuliano, C.; Rizzi, R., Efficient deterministic algorithms for finding a minimum cycle basis in undirected graphs, (Eisenbrand, F.; Shepherd, F., Integer programming and combinatorial optimization. Lecture notes in computer science, vol. 6080, (2010), Springer Berlin, Heidelberg), 397-410 · Zbl 1284.05261 |
| [2] | Audy, J.-F.; D’Amours, S.; Lehoux, N.; Rönnqvist, M., Generic mechanisms for coordinating operations and sharing financial benefits in collaborative logistics, (Camarinha-Matos, L.; Boucher, X.; Afsarmanesh, H., Collaborative networks for a sustainable world. IFIP advances in information and communication technology, vol. 336, (2010), Springer Boston), 537-544 |
| [3] | Ballot, E.; Fontane, F., Reducing transportation CO2 emissions through pooling of supply networksperspectives from a case study in French retail chains, Prod Plan Control, 21, 6, 640-650, (2010) |
| [4] | Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.; Vance, P. H., Branch-and-pricecolumn generation for solving huge integer programs, Oper Res, 46, 3, 316-329, (1998) · Zbl 0979.90092 |
| [5] | Bartolini, E.; Cordeau, J.-F.; Laporte, G., An exact algorithm for the capacitated arc routing problem with deadheading demand, Oper Res, 61, 2, 315-327, (2013) · Zbl 1267.90016 |
| [6] | Bartolini, E.; Cordeau, J.-F.; Laporte, G., Improved lower bounds and exact algorithm for the capacitated arc routing problem, Math Progr, 137, 1-2, 409-452, (2013) · Zbl 1262.90100 |
| [7] | Bode, C.; Irnich, S., Cut-first branch-and-price-second for the capacitated arc-routing problem, Oper Res, 60, 5, 1167-1182, (2012) · Zbl 1257.90008 |
| [8] | du Merle, O.; Villeneuve, D.; Desrosiers, J.; Hansen, P., Stabilized column generation, Discrete Math, 194, 1-3, 229-237, (1999) · Zbl 0949.90063 |
| [9] | Ergun, O.; Kuyzu, G.; Savelsbergh, M., Reducing truckload transportation costs through collaboration, Transp Sci, 41, 2, 206-221, (2007) |
| [10] | Ergun, O.; Kuyzu, G.; Savelsbergh, M., Shipper collaboration, Comput Oper Res, 34, 6, 1551-1560, (2007) · Zbl 1163.90363 |
| [11] | Erhun, F.; Keskinocak, P., Collaborative supply chain management, (Kempf, K. G.; Keskinocak, P.; Uzsoy, R., Planning production and inventories in the extended enterprise. International series in operations research and management science, vol. 151, (2011), Springer US), 233-268 |
| [12] | Fernandes, C. G.; Lee, O.; Wakabayashi, Y., Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, Discrete Appl Math, 157, 2, 272-279, (2009) · Zbl 1168.05318 |
| [13] | Hezarkhani, B.; Slikker, M.; Van Woensel, T., On characterization of the core of Lane covering games via dual solutions, Oper Res Lett, 42, 8, 505-508, (2014) · Zbl 1408.90038 |
| [14] | Hochbaum, D. S.; Olinick, E. V., The bounded cycle-cover problem, INFORMS J Comput, 13, 2, 104-119, (2001) · Zbl 1238.90131 |
| [15] | Immorlica, N.; Mahdian, M.; Mirrokni, V., Cycle cover with short cycles, (Diekert, V.; Durand, B., STACS 2005. Lecture notes in computer science, vol. 3404, (2005), Springer Berlin, Heidelberg), 641-653 · Zbl 1118.68763 |
| [16] | Kuyzu, G.; Akyol, C. G.; Ergun, O.; Savelsbergh, M., Bid price optimization for truckload carriers in simultaneous transportation procurement auctions, Transp Res Part B: Methodol, 73, 34-58, (2015) |
| [17] | Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Oper Res, 53, 6, 1007-1023, (2005) · Zbl 1165.90578 |
| [18] | Mladenović, N.; Hansen, P., Variable neighborhood search, Comput Oper Res, 24, 11, 1097-1100, (1997) · Zbl 0889.90119 |
| [19] | Ozener, O. O.; Ergun, O., Allocating costs in a collaborative transportation procurement network, Transp Sci, 42, 2, 146-165, (2008) |
| [20] | Ozener, O. O.; Ergun, O.; Savelsbergh, M., Lane-exchange mechanisms for truckload carrier collaboration, Transp Sci, 45, 1, 1-17, (2011) |
| [21] | Rajapakshe, T.; Dawande, M.; Gavirneni, S.; Sriskandarajah, C.; Panchalavarapu, P. R., Dedicated transportation subnetworksdesign, analysis, and insights, Prod Oper Manag, 23, 1, 138-159, (2014) |
| [22] | Sutherland JL, Goldsby T, Stank T. Leveraging collaborative transportation management (ctm) principles to achieve superior supply chain performance. In: ASCET 2004, vol. 6; 2004. |
| [23] | Thomassen, C., On the complexity of finding a minimum cycle cover of a graph, SIAM J Comput, 26, 3, 675, (1997) · Zbl 0870.05040 |
| [24] | Xu, H.; Chen, Z.-L.; Rajagopal, S.; Arunapuram, S., Solving a practical pickup and delivery problem, Transp Sci, 37, 3, 347-364, (2003) |
| [25] | Xu, S. X.; Huang, G. Q., Efficient auctions for distributed transportation procurement, Transp Res Part B: Methodol, 65, 47-64, (2014) |
| [26] | Zils M, Wallmann C. Identifying and assessing horizontal collaboration partnerships. In: 2nd Annual horizontal collaboration in the supply chain summit; 2010. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
