Hello everyone!
My name is Roman Udovichenko and I am glad to inform you that the first optimization round of Yandex.Algorithm is in full swing! This time we offer you to solve the problem prepared by the Yandex self-driving cars team.
We hope that driverless future is not too far, so we ask you to develop an algorithm for optimal management of the fleet of driverless taxis. Of course, the task is very simplified and real self-driving cars development is way more sophisticated, but the duration of our round is not too long either: you have only one week to solve it. Basic solution to this problem is pretty straightforward, but I believe there are many possible improvements. Will you be able to come up with some really interesting idea? It's all up to you and the remaining time is more than enough :)
The authors of the top scoring solutions in the optimization track will receive a cash prize, and the top 128 — cool t-shirts with the Yandex.Algorithm logo.
Good luck and, of course, have fun!
There are two optimizations rounds, right? How does it work? Do we get gp30 scores for each?
Yes, rules are the same as for algorithm rounds.
Probably GP30 scores, since there's nothing explicitly written about them. Still, there are no finals and only the top 3 people get non-Tshirt prizes.
The last submission will be used for systest, but when I want to resubmit my old solution with a higher score, it says I can't, nice
Now you can. Hope it helps :)
that was fast, thanks :)
Can you guys post your approach?
Well, I guess that my solution is mediocre, but whatever (it got slightly above 11k points in open testing stage).
Basically, I assigned an object (a passenger or a zone) to each taxi. On each iteration I shuffled the objects between taxis so that the minimal distance (let's call it dP) between a taxi and an object is as small as possible.
Then I iterated over taxis and checked, whether it's profitable to move a certain taxi in dP direction.
Sometimes no taxis can be moved in dP direction (because of some restrictions). In this case, I just moved the taxi, which is ruining the move, in a random direction by a small vector.
That's basically it.
How did you choose dP direction ? As I've understood this is direction for whole group moving ?
dP is the the shortest possible vector, that connects a taxi and an object.
This is not a direction for the whole group. Instead, it's a direction for a subgroup of taxis. You can greedily decide, whether to include a taxi in this subgroup or not.
My approach.
Taxi driving.
How we can effectively drive a car to some point?
I iterate over all moves starting after last one that contains this car up to end and add car to it if it's profitable.
Then simply add new move directly to target point.
Travel selection.
For each possible travel (car -> fan/zone) I calculated penalty using driving method described above and choose one with lowest score.
Do travel.
Do step 1 for selected travel. If target point occupied then first we push another car to nearby free position.
Do steps 2 and 3 until all fans delivred.
This approach gives around 12k point on pretests.
Improvement
I realized that if we apply some random factor to travel selection then the results are widely scattered.
So I producing solutions until time limit nearly reached and select the best one.
Basically that's all, it's gives around 13k points on pretests.
The most hard part for me is "on fly" detect if cars coordinates coincides. I spent a lot of time to try to guarantee correctness of result but still it's not perfect, in about 0.1% of cases my solution can not produce valid result.
Will we be able to submit solutions afyer the contest has ended?
For training purposes
Upsolving has been opened, feel free to submit your solutions.