An exact method for a problem of time-slot pricing
Olivier Bilenne  1@  , Frédéric Meunier  2@  
1 : Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS)
École des Ponts ParisTech (ENPC)
2 : Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique  (CERMICS)
École des Ponts ParisTech (ENPC)
6 et 8 avenue Blaise Pascal Cité Descartes - Champs sur Marne 77455 Marne la Vallée Cedex 2 -  France

We consider a market where a population of customers is willing to purchase a service offered at n different times y_1,y_2,...,y_n under limited capacities. Our task is to anticipate and to implement a pricing profile (p_1,...,p_n) that will optimally spread the expected hourly demand for the service. The time slot pricing problem is looked upon from the perspective of the service provider, in a competitive environment where profit maximization is a prime concern for the company. Each customer has a preferred time x ∈ ℝ for receiving the service, and is expected to either choose a time slot j that minimizes their total incurred cost p_j + d(x-y_j), where the strictly convex function d is an expression of the inconvenience of rescheduling from their preferred time; or to reject the service if no time slot looks satisfying. Our goal is to implement a pricing profile which maximizes the profit of the service provider by solving a bi-level decision problem sharing similarities with the optimal transport framework. We develop an exact method of solution based on dynamic programming that produces a profit-maximizing pricing profile in poly(n,|P|) basic operations if the price values are available at each time slot for decision making are taken from a set P. Extensions to differenciated or random service times are straightforward. Our approach also applies for P ≡ ℝ through discretization of the pricing space, then producing near-optimal solutions together with lower and upper bounds for the optimal value of the initial continuous-price problem. Under strongly convex d, pointwise convergence of these bounds towards the optimum typically occurs at rate O(δ) linear in the discretization step δ, slowing down to O(√δ) in some irregular cases where ε-optimality of the profit can still be guaranteed within polynomial computation time. Numerical experiments are under way for a problem of time slot pricing at electric vehicle charging stations.


Personnes connectées : 172 Vie privée
Chargement...