My workstation has no Chinese input, so I will write this down using English. I guess there should be no problem since all of the problem statements are in English.
It seems that the evaluation program doesn't correctly process the situation when MORE THAN ONE PACKAGES are delivered to the SAME PLACE at the SAME TIME.
For example, my program finds that if the following two O2O orders are processed together, it can actually save a lot of time than when they are processed individually.
E4641,B2706,S631,18:27,19:57,6 - package processing time 12
E4490,B2706,S621,18:29,19:59,2 - package processing time 9
18:27 = 627
19:57 = 717
18:29 = 629
19:59 = 719
If processed individually, the first order takes time as follows:
1. Arrives at S631 at 627, then takes the package and leaves for B2706;
2. Takes 122 minutes and arrives at B2706 at (627 + 122) 749; penalty = 5 * (749 - 717) = 160;
3. Travel time 122 + delivery time 12 = 134;
4. Total cost of the task = 134 + 160 = 294.
Likewise, the second order takes time as follows:
1. Arrives at S621 at 629, then takes the package and leaves for B2706;
2. Takes 121 minutes and arrives at B2706 at (629 + 121) 750; penalty = 5 * (750 - 719) = 155;
3. Travel time 121 + delivery time 9 = 130;
4. Total cost of the task = 130 + 155 = 285.
The total time for these two tasks is 294 + 285 = 579.
My program generates the following plan. (For simplicity, just assume that a courier take the first o2o order for the first time of the day.)
D0001,S631,8,627,6,E4641
D0001,S621,628,629,2,E4490
D0001,B2706,750,759,-2,E4490
D0001,B2706,750,762,-2,E4641
1. Arrives at S631 from nearest shop at 8(or 627), takes the package and leaves at 627 for S621;
2. Takes 1 minute and arrives at S621 at 628; takes the package and leaves at 629 for B2706;
3. Takes 121 minutes and arrives at B2706 at (629 + 121) 750; penalty for E4490 = 5 * (750 - 719) = 155; takes 9 minutes to deliver the package;
4. Stays at B2706; penalty for E4641 = 5 * (750 - 717) = 165; takes 12 minutes to deliver the package;
5. Total cost of the tasks = 1 + 1(waiting time at S621) + 121 + 9 + 12 + 155 + 165 = 464.
As you can see, my plan is totally valid and it could save 579 - 464 = 115 minutes; but when I run the evaluation program, it generates the following errors:
error: for one postman, the solution must be sorted by arrival time!
error: one order must be deliveried one time!
The courier arrives at B2706 with two packages to deliver, he has to stay at that place to make two deliveries. So how should this plan be composed without violating the the checking rules. The evaluation program correctly calculates the delay penalty, but it also calculates a penalty_rout of 90 and a penalty_serv of 30. You see, my plan should have saved me a cost of 115 because it totally follows all of the designated rules, but in the end I have to pay 5 (90 + 30 - 115) more. If an elaborate algorithm can't get paid, it's clearly not the purpose of this competition.
The clock is ticking, still haven't generate my first submission. Can anyone take a look and hurry it up?
-------------------------
-------------------------
-------------------------
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。