Search

The paper deals with a sequencing and routing problem originated by a real-world application context. The problem consists in defining the best sequence of locations to visit within a warehouse for the storage and/or retrieval of a given set of items during a specified time horizon, by considering some specific requirements and operating policies which are typical of the kind of warehouse under study. A fleet composed of both electric (i.e., equipped with a lithium-ion battery) and conventional (i.e., with internal combustion engine) forklifts is considered. We model the problem in terms of constrained multicommodity flows on a space-time network, and we extend a matheuristic approach proposed for the case of only conventional vehicles. Preliminary computational results are also presented.

We consider a game-theory model of congestion control in communica- tion networks, where each player is a user who wishes to maximize his/her flow over a path in the network. We allow for stochastic fluctuations of the cost function of each player, which consists of two parts: a pricing and a utility term. The solution concept we look for is the mean value of the (unique) variational Nash equilibrium of the game. Furthermore, we assume that it is possible to invest a certain amount of money to improve the network by enhancing the capacity of its links and, because of limited financial resources, an optimal choice of the links to improve has to be made. We model the investment problem as a nonlinear knapsack problem with gen- eralized Nash equilibrium constraints in probabilistic Lebesgue spaces and solve it numerically for some examples.

In this paper we propose an approximation procedure for a class of monotone variational inequalities in probabilistic Lebesgue spaces. The implementation of the functional approximation in Lp, with p > 2, leads to a finite dimensional variational inequality whose structure is different from the one obtained in the case p = 2, already treated in the literature. The proposed computational scheme is applied to the random traffic equilibrium problem with polynomial cost functions.

Braess' paradox is a classical result in the theory of congestion games. It motivates theoretically why adding a resource (e.g., an arc) to a network may sometimes worsen, rather than improve, the overall network performance. Differently from previous literature, which studies Braess' paradox in a non-cooperative game-theoretic setting, in this work, a framework is proposed to investigate its occurrence by exploiting cooperative games with transferable utility (TU games) on networks. In this way, instead of focusing on the marginal contribution to the network utility provided by the insertion of an arc when a single initial scenario is considered, the arc average marginal utility with respect to various initial scenarios, that is, its Shapley value in a suitably-defined TU game, is evaluated. It is shown that, for choices of the utility function of the TU game modeling congestion, there are cases for which the Shapley value associated with an arc is negative, meaning that its average marginal contribution to the network utility is negative.

The paper deals with a traffic network with random demands in which some of the roads need maintenance jobs. Due to budget constraints, a central authority has to choose which of them are to be maintained in order to decrease as much as possible the average total travel time spent by all the users, assuming that the network flows are distributed according to the Wardrop equilibrium principle. This optimal road maintenance problem is modeled as an integer nonlinear program, where the objective function evaluation is based on the solution of a stochastic variational inequality. We propose a regularization and approximation procedure for its computation and prove its convergence. Finally, the results of preliminary numerical experiments on some test networks are reported.

The adoption of smart device technologies is steadily increasing. Most of the smart devices in use today have built-in sensors which measure motion, direction, and various environmental conditions. Sensors are able to provide raw data with different quality and accuracy. A large group of smart devices forms a mobile crowdsensing system which is capable of sensing, collecting and sharing the environmental data to perform large scale sensing jobs. This paper aims to study and design an incentive mechanism for a mobile crowdsensing system based on a one-leader multi-follower Stackelberg game. A platform provider, as proponent of the sensing job, will act as the leader, while the mobile users will act as the followers. The final goal is to devise an efficient mechanism able to motivate the smart device users to participate in the sensing activity. Different from existing approaches, we propose a centralized method where the platform provider can estimate users’ parameters very efficiently sending and receiving a few messages. We formulate the optimization problem on the platform provider side as a mixed integer nonlinear program with time constraints for each job and a budget constraint. Finally, a heuristic algorithm based on the derivative-free directional direct search method is designed to solve the platform optimization problem and achieve a close-to-optimal solution for the game. Results show that our Stackelberg game solution is much more scalable than the approach proposed in the work by other authors Zhan et al. (2018) as we can decrease the average number of messages by a factor between 53 to 80 and the average running time between 23 and 650 times. Furthermore, we compared our heuristic algorithm with BARON, a state of the art commercial tool for mixed integer global optimization, to solve the platform optimization problem. Results demonstrated that our proposed algorithm converges to a near-optimal solution much faster especially in large scale systems.

In the theory of congestion games, the Braess’ paradox shows that adding one resource to a network may sometimes worsen, rather than improve, the overall network performance. Here the paradox is investigated under a cooperative game-theoretic setting, in contrast to the non-cooperative one typically adopted in the literature. A family of cooperative games on networks is considered, whose utility function, defined in terms of a traffic assignment problem and the associated Wardrop equilibrium, expresses the average quality of service perceived by the network users.

We investigate a generalized Nash equilibrium problem where players are modeled as nodes of a network and the utility function of each player depends on his/her own action as well as on the actions of his/her neighbors in the network. In the case of a quadratic reference model with shared constraints we are able to derive the variational solution of the game as a series expansion which involves the powers of the adjacency matrix, thus extending a previous result. Our analysis is illustrated by means of some numerical examples.

We investigate a class of network games with strategic complements and bounded strategy sets by using the variational inequality approach. In the case where the Nash equilibrium of the game has some boundary components, we derive a formula which connects the equilibrium to the Katz-Bonacich centrality measure, thus generalizing the classical result for the interior solution case. Furthermore, we prove that any component of the Nash equilibrium is less than or equal to the corresponding component of the social optimal solution and numerically study the price of anarchy for a small size test problem.

We consider a popular model of congestion control in communication networks within the theory of generalized Nash equilibrium problems with shared constraints, where each player is a user who has to send his/her flow over a path in the network. The cost function of each player consists of two parts: a pricing and a utility term. Within this framework we assume that the network system manager can invest a given amount of money to improve the network by enhancing the capacity of its links and, because of limited financial resources, has to make a choice as to which of the links to improve. This choice is made with the help of a performance function which is computed for each set of improvements under consideration and has the property that, once the equilibrium has been reached, maximizes the aggregate utility and minimizes the sum of delays at the links. We model this problem as a nonlinear knapsack problem with generalized Nash equilibrium constraints and show some preliminary numerical experiments.