Corporate mobility is often based on a fixed assignment of vehicles to employees. Relaxing this fixation and including alternatives such as public transportation or taxis for business and private trips could increase fleet utilization and foster the use of battery electric vehicles. We introduce the mobility offer allocation problem as the core concept of a flexible booking system for corporate mobility. The problem is equivalent to interval scheduling on dedicated unrelated parallel machines. We show that the problem is NP-hard to approximate within any factor. We describe problem specific conflict graphs for representing and exploring the structure of feasible solutions. A characterization of all maximum cliques in these conflict graphs reveals symmetries which allow to formulate stronger integer linear programming models. We also present an adaptive large neighborhood search based approach which makes use of conflict graphs as well. In a computational study, the approaches are evaluated. It was found that greedy heuristics perform best if very tight run-time requirements are given, a solver for the integer linear programming model performs best on small and medium instances, and the adaptive large neighborhood search performs best on large instances.


翻译:公司流动性往往基于固定的车辆给雇员分配。放松这种固定性,包括公共车辆或商务和私人旅行出租车等替代办法,可以提高车队利用率,促进使用电池电动车辆。我们引入流动性问题,作为公司流动性灵活预订系统的核心概念。问题相当于对不相关的专用平行机器的间隔时间安排。我们发现,问题很难在任何因素中估计。我们描述了代表并探索可行解决方案结构的特定问题冲突图。这些冲突图表中所有最大分类的特征的定性显示,能够形成更强的整形线性编程模型。我们还介绍了适应性大型社区搜索方法,同时使用冲突图表。在计算研究中,对方法进行了评估。发现,贪婪的超自然主义效果最好,只要给出了极紧的运行时间要求,就能够满足任何因素。我们描述了以中小实例为最佳表现的整形线性编程编程模型的解决方案,适应性大型社区搜索则在大实例中进行最佳表现。

0
下载
关闭预览

相关内容

专知会员服务
52+阅读 · 2020年9月7日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
6+阅读 · 2018年12月3日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
老铁,邀请你来免费学习人工智能!!!
量化投资与机器学习
4+阅读 · 2017年11月14日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Fairer LP-based Online Allocation
Arxiv
0+阅读 · 2021年10月27日
Average-Case Subset Balancing Problems
Arxiv
0+阅读 · 2021年10月27日
Arxiv
0+阅读 · 2021年10月27日
Arxiv
0+阅读 · 2021年10月25日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2020年9月7日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
6+阅读 · 2018年12月3日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
老铁,邀请你来免费学习人工智能!!!
量化投资与机器学习
4+阅读 · 2017年11月14日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关论文
Top
微信扫码咨询专知VIP会员