Collaboration in transportation between two or more agents is becoming an important approach to find efficient solutions or plans. Efficiency can be measured in, for example, lower cost or more ...flexibility. An important aspect of the collaboration is to decide on how to share the benefits—for example, cost, profit, or resources. There are many sharing mechanisms or cost allocations proposed in the literature. Some are based on simple proportional rules and others are based on theoretical concepts found in game theory. We provide a survey on cost allocation methods found in the literature on collaborative transportation, including problems on planning, vehicle routing, traveling salesman, distribution, and inventory. A total of 55 scientific articles compose the main part of the survey, most of them published between 2010 and 2015. We identify more than 40 cost allocation methods used in this stream of literature. We describe the theoretical basis for the main methods as well as the cases where they are used. We also report savings from the collaborations when they are based on industrial data. Some directions for future research are discussed.
•Sports timetabling algorithms are highly tailored and data sets are rarely shared.•A literature classification identifies popular formats, constraints, and objectives.•XML file templates facilitate ...sharing of problem instance data and solutions.•A website automates validation and exchange of problem instances and solutions.•New best found solutions can be submitted to track algorithm performance over time.
Sports timetabling problems are combinatorial optimization problems which consist of creating a timetable that defines against whom, when, and where teams play games. In the literature, sports timetabling problems have been reported featuring a wide variety of constraints and objectives. This variety makes it challenging to identify the relevant set of papers for a given sports timetabling problem. Moreover, the lack of a generally accepted data format makes that problem instances and their solutions are rarely shared. Consequently, it is hard to assess algorithmic performance since solution methods are often tested on just one or two specific instances. To mitigate these issues, this paper presents RobinX, a three-field notation to describe a sports timetabling problem by means of the tournament format, the constraints in use, and the objective. We use this notation to classify sports timetabling problems presented in the operations research literature during the last five decades. Moreover, RobinX contains xml-based file templates to store problem instances and their solutions and presents an online platform that offers three useful tools. First, a query tool assists users to select the relevant set of papers for a given timetabling problem. Second, the online platform provides access to an xml data repository that contains real-life problem instances from different countries and sports. Finally, the website enables users to interact with a free and open-source C++-library to read and write xml files and to validate and evaluate encoded instances and solutions.
•Integer programming produces schedule of FIFA World Cup South American Qualifiers.•A mirrored schedule without double round breaks is infeasible.•New schedule reduces double round breaks from 18 to ...zero compared to old schedule.•New schedule unanimously approved by the ten South American countries.•New schedule currently being used for the qualifiers to 2018 FIFA World Cup Russia.
Every four years, the 10 national teams members of the South American Football Confederation (CONMEBOL) compete for one of the South American slots in the final phase of the FIFA World Cup. The qualifying competition consists of a double round robin tournament. The matches are scheduled in 9 closely spaced pairs known as double rounds. Every team plays twice in each double round. The tournament is spread over 2 years, so the double rounds are months apart. After using the same mirrored schedule for about twenty years, and persistent complaints from its members, CONMEBOL decided to change the schedule for the 2018 World Cup. Supported by one of CONMEBOL’s members, we used integer programmming to construct schedules that overcome the main drawbacks of the previous approach. After exploring many design criteria, we proposed a candidate schedule based on a French scheme. The main feature of the proposed schedule is that every team plays once at home and once away on each double round, a departure from traditional symmetric (mirrored) schemes. This proposal was unanimously approved by CONMEBOL members and is currently being used in the qualifier tournament for the 2018 FIFA World Cup in Russia.
The top two divisions of the Argentinean professional basketball system have since 2014–2015 used a season schedule format similar to that used by the NBA in which games are played all through the ...week, replacing the previous setup where all games were scheduled on weekends. This change has confronted the Argentinean league organizers with new scheduling challenges, one of which is the assignment of referees to games. The present article addresses this assignment problem using a tool based on an integer linear programming model. The objective is to minimize the total cost of trips made by the referees while also satisfying a series of other conditions. The problem is broken down into a series of relatively small subproblems representing successive periods of the season, and the solution is obtained using a rolling horizon heuristic. The approach was tested by applying it to the First Division’s 2015–2016 season, the last one before introducing the approach presented in this article, when referees were still assigned using manual methods. The travel costs simulated by the model were 26% lower than the total travel costs actually incurred under the manual assignments, and all of the restrictions that had been requested by league officials were satisfied. The model was used by the First Division for the 2016–2017 and 2017–2018 seasons and in 2017–2018 also by the Second Division.
Bioenergy is becoming a more important energy source. An important bioenergy assortment in Sweden is given by primary forest fuels. These account for about 14% of the biofuels or about 4% of Sweden's ...total energy. There are large volumes of forest fuel available. However, it is a low-value commodity and it is very sensitive to logistic cost to make it profitable. In this article, we analyse alternatives to lower the logistic costs. This includes the scheduling of the harvest and chipping operations in relation to transportation, delivered mix of assortments to customers and collaboration. We study these alternatives in a case that accounts for all operations in Sweden, involving 200,000 registered transports of about 6.1 million tons of forest biomass, equivalent to 17.4 TWh of energy consumption. We define a number of instances for these alternatives and formulate an optimization model based on linear programming. The solution is obtained by using a decision support system. We identify savings potential of about 22% from changing the operations. These savings can have a large impact on the industry and, more importantly, increase the use of bioenergy. We also test cost allocation methods to spread the savings based on cooperative game theory concepts.
•A country-wide study of the forest fuel transports in Sweden is done.•It involves 200,000 transports of 6.1 million ton of biomass equivalent to 17.4 TWh.•Efficient logistic is crucial to make forest fuel a competitive source of bioenergy.•Up to 22% savings are found by better schedules, assortments mix and collaboration.•Savings can have large impact on the industry and increase the use of bioenergy.
This article investigates economic and operational effects of introducing autonomous vessels to liner shipping networks. By the formulation of optimization models, we analyze how fleet configurations ...with vessels of different capacity affect the cost and service level of liner shipping networks in both static and dynamic settings. We implement the model in a data instance that extends a data instance on the Baltic trade from conventional to autonomous vessels. Our results show that the introduction of autonomous vessels might lead to cost savings of 7.1% with respect to the fleet of conventional vessels. The main savings come from lower time charter costs and lower bunker costs. The results also suggest that a fleet configuration combining large with small vessels perform better, because of its better ability to accommodate to the asymmetry of the trade. The implementation of a flexible sailing schedule in the dynamic setting might lead to a great increase in the service level of the network, but at the expense of an increase in costs.
•MIP models are proposed to decide coalition structure in cooperative games.•The models are tested in forest transportation and in inventory for oil operations.•Results show a stable structure under ...strong equilibrium may become infeasible.•Maximum cardinality bound on coalitions has important effects in the structure.•Savings of adding one more player significantly decrease with the cardinality bound.
Given a set of players and the cost of each possible coalition, the question we address is which coalitions should be formed. We formulate mixed integer linear programming models for this problem, considering core stability and strong equilibrium. The objective function looks for minimizing the total cost allocated among the players. Concerned about the difficulties of managing large coalitions in practice, we also study the effect of a maximum cardinality constraint per coalition. We test the models in two applications. One is in collaborative forest transportation and the other one in inventory of spare parts for oil operations. In these situations, collaboration opportunities involving significant savings exist, but for several reasons, it may be better to group the players in different sub-coalitions rather than in the grand coalition. The models we propose are thus relevant for deciding how to partition the set of players. We also prove that if the strong equilibrium model is feasible, its optimal cost is equal to the optimal cost of the core stability model and, consequently, a coalition structure that solves one problem also solves the other problem. We present results that illustrate this property. We also present results where the core stability problem is feasible and the strong equilibrium problem is infeasible. Setting an upper bound on the maximum cardinality of the coalitions, allows us to study the marginal savings of enlarging the cardinality of the coalitions. We find that the marginal savings of allowing one more player significantly decreases as the bound increases.
•We propose a horizontal collaborative approach for the wine bottling scheduling problem.•We use a cooperative game approach where the characteristic function is computed heuristically.•We propose a ...maximum entropy methodology which simultaneously solves the partner selection and cost allocation problems.•Numerical experiments reveal that collaboration can have important positive effects.
This paper proposes a horizontal collaborative approach for the wine bottling scheduling problem. The opportunities for collaboration in this problem are due to the fact that many local wine producers are usually located around the same region and that bottling is a standard process. Collaboration among wineries is modeled as a cooperative game, whose characteristic function is derived from a mixed integer linear programming model. Real world instances of the problem are, however, unlikely to be solved to optimality due to its complex combinatorial structure and large dimension. This motivates the introduction of an approximated version of the original game, where the characteristic function is computed through a heuristic procedure. Unlike the exact game, the approximated game may violate the subadditivity property. Therefore, it turns relevant not only to find a stable cost allocation but also to find a coalition structure for selecting the best partition of the set of firms. We propose a maximum entropy methodology which can address these two problems simultaneously. Numerical experiments illustrate how this approach applies, and reveal that collaboration can have important positive effects in wine bottling scheduling decreasing delay by 33.4 to 56.9% when improvement heuristic solutions are used. In contrast to the exact game in which the grand coalition is always the best outcome, in the approximated game companies may be better forming smaller coalitions. We also devise a simple procedure to repair the characteristic function of the approximated game so that it recovers the subadditivity property.
The most studied problem in sports scheduling, so-called traveling tournament problem (TTP), aims at finding schedules minimizing the total distance traveled by the teams. While minimizing all the ...traveling between games is efficient from the overall perspective, it overlooks the distribution of the travel among the teams. Consequently, some teams may end up better than others with respect to their individual goals, an imbalance which may affect teams’ often-limited resources or preparedness for the games. This article adopts a cooperative game theory framework to obtain tournament schedules where the distances traveled by the teams are allocated according to fairness criteria. The approach consists of three steps. First, the scheduling problem is reformulated as a transferable utility game. Second, by means of well-established allocation methods, an ideal distance distribution among the teams is determined. Third, we introduce fairness measures to produce a schedule which approximately resembles the ideal distribution. We also discuss the case of not pursuing fairness, but rather a compromise between fairness and minimum total distance. We illustrate the approach by a numerical example in one of the classic TTP data instances.
•Overlapping coalitions for first time studied in collabortive transportation.•Integer linear models help finding the best coalition configuration.•Coalition configuration adds flexibility and ...improves results of coalition structures.•Large case on forest biomass: 27 companies, 200,000 transports, 6 million tons, 17 terawatt hours.•Potential benefits: 8% cost savings.
Most literature on collaborative transportation has focused on cost allocation, assuming as given which companies take part in the collaboration. However, a primary problem is the formation of coalitions. In this article, we study the so-called coalition configuration problem, in which any company can collaborate in more than one coalition. This is more general than the classic coalition structure problem, where a company must belong to only one coalition. We develop two approaches for coalition configuration in transportation. One is area-driven, which assumes the whole territory is divided into areas and then finds coalitions within each area by integer linear models. The other approach consists of a mixed integer linear programming model that embeds the coalition configuration in the transportation problem. Our motivation comes from a real world case in the forest fuels industry in Sweden, involving 27 companies, 200,000 transports, and 6 million tonnes of forest biomass, equivalent to 17 terawatt hours of energy consumption. Collaborative transportation renders about 8% of potential cost savings in this case, and may also help to increase the use of bioenergy. The coalition configuration increases by about 2.5% the savings obtained by the coalition structure and is competitive with the savings of the grand coalition.
