linear programming for bus tickets

Question

Hi I work as a programmer at a bus company and I need to implement a ride initialization request. I think it might be a linear programming problem but I'm not sure and I ask for some help :)

A passenger sends my server a request to initialize a bus ride.

The request includes the different entities for the ride. For example a request might be :

Request = [2 Adults, 3 Children, 1 Dog, 2 Bikes]

My server knows what are the different tickets the passenger has. Each ticket has a cost (the price the passenger bought it with) and a list of entities it enables a ride for.

For example, a passenger might possess :

Ticket1- cost 10, enables [1 Adult, 1 Bike]
Ticket2- cost 20, enables [1 Child]
Ticket3- cost 10, enables [1 Adult, 1 Dog]

I would love some help designing an algorithm that finds the optimal collection of tickets to use for the ride (optimal being the cheapest combination), or return error if the ride isn't feasible.

I think this could be represented as a linear programming problem and then I can just use the simplex algorithm to find the optimal solution. But I'm not sure how to do it... please help me I'm not much of a math expert :/

Thank you!

Answer 1

The example you have given can be turned very easily into a linear programming problem.

Version 1:

Let Num1 be the number of Ticket1, Num2 be the number of Ticket 2 etc.

Minimise TotalCost

st

TotalCost = 10 Num1 + 20 Num2 + 10Num3

Num1+Num3 $\ge 2$ (this ensures the correct number of adults)

Num2 $\ge 3$ (this ensures the correct number of children)

Num3 $\ge 1$ (this ensures the correct number of dogs)

Num1 $\ge 2$ (this ensures the correct number of bikes)

Version 2:

Reading your comments, I have realised the subtlety that a passenger already holds a certain number of tickets. Let’s use the variable NumHeld1, NumHeld2 etc to represent these numbers.

We can assume that a passenger would prefer to use up held tickets (presumably prepaid) before buying new ones, but would also prefer to go for a least cost model. This preference can be modelled by setting an objective function where already held tickets appear to cost less than new tickets:

TotalCost = 10 Num1usingNew + 9 Num1usingHeld + 20 Num2usingNew + 18Num1usingHeld + 10Num3usingNew + 9Num3usingHeld

(I’ve reduced the apparent cost of the held tickets by 10% but you can alter that depending on how difficult it is for customers to buy new tickets or how desperate they are to use up their existing stock)

Num1+Num3 $\ge 2$ (this ensures the correct number of adults)

Num2 $\ge 3$ (this ensures the correct number of children)

Num3 $\ge 1$ (this ensures the correct number of dogs)

Num1 $\ge 2$ (this ensures the correct number of bikes)

Num1=Num1usingNew + Num1usingHeld

Num2=Num2usingNew + Num2usingHeld

Num3=Num3usingNew + Num3usingHeld

Num1usingHeld $\le$ NumHeld1

Num2usingHeld $\le$ NumHeld2

Num3usingHeld $\le$ NumHeld3