不能随意解除，遗赠扶养协议是一种平等、有偿和互为权利义务关系的民事法律关系。遗赠扶养协议是我国《民法典》(2021年1月1日生效)确立的一项新的法律制度，是我国继承制度的新发展。
根据最高人民法院《关于贯彻执行<继承法>若干问题的意见》第56条之规定，扶养人或集体组织与公民订有遗赠扶养协议，扶养人或集体组织无正当理由不履行，致协议解除的，不能享有受遗赠的权利，其支付的供养费用一般不予补偿;遗赠人无正当理由不履行，致协议解除的，则应偿还扶养人或集体组织已支付的供养费用。
遗赠扶养协议是一种平等、有偿和互为权利义务关系的民事法律关系，对遗赠人和扶养人双方均具有约束力，双方应当按约定切实履行，小刘能够证明自己履行了扶养义务，并能提供发票证明自己为刘大爷支付了医药费、生活费、旅游费等费用，刘大爷无正当理由单方要求解除遗赠扶养协议，应当偿还小刘已支付的供养费用。
二、什么情况下可以解除
1、双方协商同意，致协议解除。
如果遗赠扶养协议当事人一方的情况发生变化(包括遗赠人另有亲属扶养或扶养人丧失扶养能力)，一方当事人有正当理由，可以要求双方协商解除协议。
如系遗赠人提出解除协议的，遗赠人应对扶养人已尽的义务在经济上给予适当补偿;如系扶养人提出解除协议的，遗赠人一般不给予扶养人经济补偿。
2、一方无正当理由不履行，致协议解除。
扶养人或集体组织与公民订有遗赠扶养协议，扶养人或集体组织无正当理由不履行，致协议解除的，不能享有受遗赠的权利，其支付的供养费一般不予补偿。
遗赠人无正当理由不履行，致协议解除的，则应偿还扶养人或集体组织已支付的供养费用。
遗赠协议签订后，双方可以协商解除遗赠扶养协议，按照双方的实际情况进行办理。一方没有按照协议内容办理时，也可以解除遗赠扶养协议，我国的法律保护遗赠扶养协议的双方，任何一方不得违背遗赠扶养协议的条款。
