0
$\begingroup$

I have an optimization problem, where i need to find set of tickets for certain period, such that sum of prices for these tickets is minimal.

Algo should accepts list of trips and list of tickets as input. And output list of tickets with min possible sum price with conditions that this list of tickets covers all trips.

Trip has following fields:

OriginZone
DestinationZone
EndOfTripTimestamp

Ticket object consists of these fields:

OriginZone
DestinationZone
MaxNumberOfTransfers  // 0 if limited by duration
MaxDuration           // 0 if limited by transfers
Price

It's considered that ticket covers trip if Ticket.OriginZone =< Trip.OriginZone and Ticket.DestinationZone >= Trip.DestinationZone. Example:

Ticket {OriginZone: 1, DestinationZone: 4, MaxNumberOfTransfers: 1, MaxDuration: 0} covers trip {OriginZone: 2, DestinationZone: 3}

MaxNumberOfTransfers specifies how much times this ticket can be used. If value it's value is 2, this ticket can cover 2 trips that happen between OriginZone and DestinationZone. MaxDuration specifies period in seconds, in which this ticket can be used from time of purchase(for example if ticket is valid for 24 hours, this field will be set to 24 * 3600). It should be considered that ticket was bought right before first trip that it's used for.

This fields are exclusive. So if MaxDuration field is set, than MaxNumberOfTransfers is not used.

Here is example, of how this algo should work:

> trips = [
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T15:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-16T16:00:00},
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T17:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-17T18:00:00}
]
> tickets = [
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
]
> algo(trips, tickets)
OUTPUT:
  {OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
  {OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},

To clarify this example, here you see 4 trips that happened in period of 2 days. In first day there's 3 trips overall, 2 from zone 1 to 2, and one from zone 3 to 4. And on second day there's one trip from zone 3 to 4. So algorithm picks 2 tickets to cover these trips -- 24 hour ticket for zones 1 to 2 and ticket with 2 transfers for zones 3 to 4.

Overall this looks like combinatorial optimization problem, but i wasn't able to find any non trivial algorithm for solving it. So, currently i'm using brute force algo that looks like:

recursive_function(trips, tickets):
    trip = trips[0]
    find best price iterating over tickets:
        price, tickets_list = recursive_function(trips[1:], tickets)

   return tickets_list with best price sum

So, my question is, is there any common problem that's similar to my and have non-trivial solution? Or maybe someone can recommend me some topics to look closely into.

$\endgroup$
4
  • 1
    $\begingroup$ What is a transfer as in MaxNumberOfTransfers? (I take MaxDuration to refer to validity - from purchase (can tickets be obtained during the trip?), first use, …?) $\endgroup$
    – greybeard
    Sep 17 '20 at 7:28
  • $\begingroup$ @D.W. I updated post, please check if i should clarify it more $\endgroup$ Sep 17 '20 at 8:41
  • $\begingroup$ @greybeard It should be assumed that ticket obtained right before first trip that it used for. $\endgroup$ Sep 17 '20 at 8:42
  • 1
    $\begingroup$ If you ignore the duration constraint and if each ticket can be used for only 1 trip, this can be expressed as an instance of the assignment problem. That might not help with your problem, though. $\endgroup$
    – D.W.
    Sep 19 '20 at 1:47
1
$\begingroup$

If you wanted to solve it in practice, I would recommend that you try using an ILP solver. You can express this as an instance of integer linear programming, then use an off-the-shelf ILP solver.

Introduce zero-or-one variables $x_i$ (indicates whether the $i$th ticket is bought or not) and $y_{ij}$ (indicates whether the $i$th ticket is used to cover the $j$th trip). Then you can write linear inequalities to express the requirements; e.g., $\sum_j y_{ij} \le d_i x_i$ where $d_i$ is the max duration of ticket $i$, and so on. The total price is a linear function of the variables, so you can minimize that objective function, subject to these inequalities.

I don't know whether there is a more efficient algorithm.

$\endgroup$
1
  • $\begingroup$ Thanks for the hint! I will do research on topic of ILP. P.S. I didn't marked your answer as accepted yet, but if there's no other answers in a few days, i will. $\endgroup$ Sep 20 '20 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.