×

A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction. (English) Zbl 1348.90534

Summary: The bi-objective winner determination problem (2WDP-SC) of a combinatorial procurement auction for transport contracts is characterized by a set \(B\) of bundle bids, with each bundle bid \(b\in B\) consisting of a bidding carrier \(c_b\), a bid price \(p_b\), and a set \(\tau_b\) of transport contracts which is a subset of the set \(T\) of tendered transport contracts. Additionally, the transport quality \(q_{t,c_b}\) is given which is expected to be realized when a transport contract \(t\) is executed by a carrier \(c_b\). The task of the auctioneer is to find a set \(X\) of winning bids \((X\subseteq B)\), such that each transport contract is part of at least one winning bid, the total procurement costs are minimized, and the total transport quality is maximized. This paper presents a metaheuristic approach for the 2WDP-SC which integrates the greedy randomized adaptive search procedure with a two-stage candidate component selection procedure, large neighborhood search, and self-adaptive parameter setting in order to find a competitive set of non-dominated solutions. The heuristic outperforms all existing approaches. For seven small benchmark instances, the heuristic is the sole approach that finds all Pareto-optimal solutions. For 28 out of 30 large instances, none of the existing approaches is able to compute a solution that dominates a solution found by the proposed heuristic.

MSC:

90C27 Combinatorial optimization
91B26 Auctions, bargaining, bidding and selling, and other market models
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

SPEA2; PERL; TTTPLOTS
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Kopfer, H.; Pankratz, G., Das Groupage—Problem kooperierender Verkehrsträger, (Kall, P.; Lüthi, H. J., Operations research proceedings 1998 (1999), Springer: Springer Berlin), 453-462 · Zbl 1024.90504
[2] Pankratz, G., Analyse kombinatorischer Auktionen für ein Multi-Agentensystem zur Lösung des Groupage-Problems kooperierender Speditionen, (Inderfurth, K.; Schwödiauer, G.; Domschke, W.; Juhnke, F.; Kleinschmidt, P.; Wäscher, G., Operations research proceedings 1999 (2000), Springer: Springer Berlin), 443-448 · Zbl 1052.91511
[3] Sheffi, Y., Combinatorial auctions in the procurement of transportation services, Interfaces, 34, 4, 245-252 (2004)
[4] Ledyard, J. O.; Olson, M.; Porter, D.; Swanson, J. A.; Torma, D. P., The first use of a combined-value auction for transportation services, Interfaces, 32, 5, 4-12 (2002)
[5] Elmaghraby, W.; Keskinocak, P., Combinatorial auctions in procurement, (Harrison, T.; Lee, H.; Neale, J., The practice of supply chain managementwhere theory and application converge (2004), Springer-Verlag: Springer-Verlag New York), 245-258
[6] Caplice, C.; Sheffi, Y., Combinatorial auctions for truckload transportation, (Cramton, P.; Shoaham, Y.; Steinberg, R., Combinatorial auctions (2006), MIT Press: MIT Press Cambridge, MA), 539-571
[7] Caplice, C.; Sheffi, Y., Optimization-based procurement for transportation services, Journal of Business Logistics, 24, 2, 109-128 (2003)
[8] Abrache, J.; Crainic, T.; Gendreau, M.; Rekik, M., Combinatorial auctions, Annals of Operations Research, 153, 34, 131-164 (2007) · Zbl 1132.91440
[9] Goossens, D.; Spieksma, F., Exact algorithms for the matrix bid auction, Computers & Operations Research, 36, 4, 1090-1109 (2009) · Zbl 1162.91356
[10] Yang, S.; Segre, A. M.; Codenotti, B., An optimal multiprocessor combinatorial auction solver, Computers & Operations Research, 36, 1, 149-166 (2009), Part Special Issue: Operations Research Approaches for Disaster Recovery Planning · Zbl 1152.91475
[11] de Vries, S.; Vohra, R. V., Combinatorial auctionsa survey, INFORMS Journal on Computing, 15, 3, 284-309 (2003) · Zbl 1238.91003
[12] Catalán, J.; Epstein, R.; Guajardo, M.; Yung, D.; Martínez, C., Solving multiple scenarios in a combinatorial auction, Computers & Operations Research, 36, 10, 2752-2758 (2009) · Zbl 1160.91339
[13] Chen, R. L.Y.; AhmadBeygi, S.; Cohn, A.; Beil, D. R.; Sinha, A., Solving truckload procurement auctions over an exponential number of bundles, Transportation Science, 43, 4, 493-510 (2009)
[14] Buer, T.; Pankratz, G., Solving a bi-objective winner determination problem in a transportation procurement auction, Logistics Research, 2, 2, 65-78 (2010)
[15] Ishibuchi, H.; Murata, T., A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Transactions on Systems, Man, and Cybernetics, Part CApplications and Reviews, 28, 3, 392-403 (1998)
[16] Jaszkiewicz, A., On the performance of multiple-objective genetic local search on the 0/1 knapsack problem—a comparative experiment, IEEE Transactions on Evolutionary Computation, 6, 4, 402-412 (2002)
[17] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithmNSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002)
[18] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2improving the strength Pareto evolutionary algorithm for multiobjective optimization, (Giannakoglou, K.; Tsahalis, D.; Periaux, J.; Papailiou, K.; Fogarty, T., Proceedings of the EUROGEN2001 Conference (2002), International Center for Numerical Methods in Engineering (CIMNE): International Center for Numerical Methods in Engineering (CIMNE) Barcelona), 95-100
[19] Jaszkiewicz, A., A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm, Annals of Operations Research, 131, 1-4, 135-158 (2004) · Zbl 1067.90149
[20] Zhang, Q.; Li, H., Moea/da multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11, 6, 712-731 (2007)
[21] Li, H.; Landa-Silva, D., An adaptive evolutionary multi-objective approach based on simulated annealing, Evolutionary Computation, 19, 4, 561-595 (2011), URL \(\langle\) http://dx.doi.org/10.1162/EVCO_a_\(00038 \rangle \)
[22] Buer, T.; Pankratz, G., Grasp with hybrid path relinking for bi-objective winner determination in combinatorial transportation auctions, Business Research, 3, 2, 192-213 (2010), \( \langle\) urn:nbn:de:\(0009-20-26859 \rangle \)
[23] Buer, T.; Kopfer, H., Shipper decision support for the acceptance of bids during the procurement of transport services, (Böse, J.; Hu, H.; Jahn, C.; Shi, X.; Stahlbock, R.; Vo, S., Proceedings of the 2nd international conference on computational logistics (ICCL’11). Lecture notes in computer science, vol. 6971 (2011), Springer), 18-28
[26] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexit of computer computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 1467.68065
[27] Serafini, P., Some considerations about computational complexity for multi objective combinatorial problems, (Jahn, J.; Krabs, W., Recent advances and historical development of vector optimization. Lecture notes in economics and mathematical systems (1986), Springer-Verlag: Springer-Verlag Berlin, Germany), 222-232
[28] Feo, T. A.; Resende, M. G., Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 2, 109-133 (1995) · Zbl 0822.90110
[29] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472 (2006)
[30] Lan, G.; DePuy, G. W.; Whitehouse, G. E., An effective and simple heuristic for the set covering problem, European Journal of Operational Research, 176, 3, 1387-1403 (2007) · Zbl 1102.90048
[31] Chvátal, V., A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 4, 3, 233-235 (1979) · Zbl 0443.90066
[32] Shaw, P., Using constraint programming local search methods to solve vehicle routing problems, (Maher, M.; Puget, J. F., Principles and Practice of Constraint Programming—CP98. Lecture notes in computer science, vol. 1520 (1998), Springer: Springer Heidelberg), 417-431
[33] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; da Fonseca, V. G., Performance assessment of multiobjective optimizersan analysis and review, IEEE Transactions on Evolutionary Computation, 7, 117-132 (2003)
[34] Zitzler, E.; Thiele, L., Multiobjective optimization using evolutionary a comparative case study, (Eiben, A.; Bäck, T.; Schoenauer, M.; Schwefel, H. P., Parallel Problem Solving from Nature—PPSN V. Lecture notes in computer science, vol. 1498 (1998), Springer: Springer Berlin/Heidelberg), 292-301
[35] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithmsa comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 4, 257-271 (1999)
[38] Hoos, H. H.; Stützle, T., Towards a characterisation of the behaviour of stochastic local search algorithms for SAT, Artificial Intelligence, 112, 1-2, 213-232 (1999) · Zbl 0996.68069
[39] Ribeiro, C.; Rosseti, I.; Vallejos, R., On the use of run time distributions to evaluate and compare stochastic local search algorithms, (Stützle, T.; Birattari, M.; Hoos, H., Engineering stochastic local search algorithms. Designing, implementing and analyzing effective heuristics. Lecture notes in computer science, vol. 5752 (2009), Springer-Verlag), 16-30
[40] Feo, T. A.; Resende, M. G.; Smith, S. H., A greedy randomized adaptive search procedure for maximum independent set, Operations Research, 42, 5, 860-878 (1994) · Zbl 0815.90121
[41] Aiex, R.; Resende, M.; Ribeiro, C., TTT plotsa perl program to create time-to-target plots, Optimization Letters, 1, 355-366 (2007) · Zbl 1220.90102
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.